[백준/Python] 21736번 : 헌내기는 친구가 필요해

문제 정보

제목 : 헌내기는 친구가 필요해

번호 : 21736번

사용 언어 : Python

문제 링크

https://www.acmicpc.net/problem/21736

21736번: 헌내기는 친구가 필요해

시간 제한	메모리 제한
1 초 (하단 참고)	1024 MB

• Java 8: 2 초
• Python 3: 2 초
• PyPy3: 2 초
• Java 8 (OpenJDK): 2 초
• Java 11: 2 초
• Python 2: 2 초
• PyPy2: 2 초
• Kotlin (JVM): 2 초
• Java 15: 2 초

 

문제

2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다. 

도연이가 다니는 대학의 캠퍼스는 N × M 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 예를 들어, 도연이가 (x, y)에 있다면 이동할 수 있는 곳은 (x+1, y), (x, y+1), (x-1, y), (x, y-1)이다. 단, 캠퍼스의 밖으로 이동할 수는 없다.

불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성해보자.

 

입력

첫째 줄에는 캠퍼스의 크기를 나타내는 두 정수 N (1 ≤ N ≤ 600), M (1≤ N ≤600)이 주어진다.

둘째 줄부터 N개의 줄에는 캠퍼스의 정보들이 주어진다. O는 빈 공간, X는 벽, I는 도연이, P는 사람이다. I가 한 번만 주어짐이 보장된다.

 

출력

첫째 줄에 도연이가 만날 수 있는 사람의 수를 출력한다. 단, 아무도 만나지 못한 경우 TT를 출력한다.

 

입출력 예제

---

나의 풀이

캠퍼스 크기를 입력받아 N, M에 각각 정수형으로 변환하여 저장합니다. 도연이의 방문 여부 체크 리스트를 생성하기 위해 for루프를 이용해서 N, M의 개수만큼 False로 I_visited 리스트에 저장합니다. 빈 리스트인 I_queue, campus를 생성해둡니다. 추후 도연이의 처음 위치와 갈 위치를 저장할 리스트와 캠퍼스의 정보를 저장할 리스트입니다. P_count 변수도 0으로 선언합니다. 갈 수 있는 방향을 저장해둔 리스트를 만들겁니다. dx, dy 이름으로 생성했습니다.

N의 길이만큼 반복하는 for루프를 이용해 한줄씩 캠퍼스의 정보를 입력받아 cam이라는 변수에 임시로 저장합니다. 이때 cam 변수는 문자열형이므로 문자를 찾는 메소드인 find()를 이용해 "I"를 찾아 index 변수에 값을 저장합니다. index의 값이 -1이 아니라면 도연이의 현재 위치를 찾은 것이므로 I_queue에 [n,index]를 추가하여 위치를 저장해둡니다. 그리고 해당 위치의 방문 여부를 True로 바꿉니다. 해당 과정을 거친 후 campus 리스트에 cam을 리스트로 변환하여 추가합니다.

for 루프가 끝나면 I_queue에 원소가 존재하는 동안 반복하는 while루프를 이용해 해결했습니다. 전 너비 우선 탐색을 사용했습니다. x,y 변수에 도연이의 현재 위치를 pop()을 통해 각각 저장합니다. 만약 해당 위치에서 사람을 만났다면 P_count를 1 증가시킵니다. 그 이후엔 갈 방향을 저장할 것입니다. 4번 반복하는 for루프를 통해 캠퍼스의 밖으로 나가지 않는 범위에서 next_x, next_y값을 구합니다. 벽이 아닌 곳 중에서 방문 안한 위치를 찾으면 그 위치의 방문 여부를 True로 변경하고 I_queue에 [next_x,next_y]를 저장합니다.

while루프의 반복이 끝나면 P_count를 출력하는데 If문을 이용해 0보다 크면 P_count를 출력하고, 0이면 "TT"를 출력하도록 합니다. 

 

코드

N, M = map(int, input().split()) # 캠퍼스 크기 ( N * M )
I_visited = [[False for _ in range(M)] for _ in range(N)] # 도연이의 방문 여부 체크 리스트
I_queue = [] # 도연이의 처음 위치, 갈 위치 저장할 리스트
P_count = 0 # 도연이가 만날 수 있는 사람의 수
campus = [] # 캠퍼스 정보 저장 리스트

# 갈 수 있는 방향 저장한 리스트
dx = [1,0,-1,0]
dy = [0,1,0,-1]

# 캠퍼스의 정보 입력받아 리스트에 저장함
for n in range(N) :
    cam = input()
    index = cam.find("I") # 도연이의 위치 찾음
    if index != -1 :
        I_queue.append([n,index]) 
        I_visited[n][index] = True
    campus.append(list(cam))


while( I_queue ) :
    x,y = I_queue.pop(0)

    if campus[x][y] == "P" : # 사람을 만남
        P_count += 1

    for i in range(4) : # 갈 방향을 정함
        if 0 <= x+dx[i] and x+dx[i] < N and 0 <= y+dy[i] and y+dy[i] < M:
            next_x = x+dx[i]
            next_y = y+dy[i]
        else :
            continue

        if( campus[next_x][next_y] != "X" and I_visited[next_x][next_y] == False) : # 벽이 아닌 곳 중에서 방문 안한 위치 찾음
            I_visited[next_x][next_y] = True
            I_queue.append( [next_x,next_y] )    
    
print(P_count if P_count>0 else "TT" ) # 아무도 맛나지 못한 경우 "TT"출력 그 외에는 수 출력