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

문제 요약

도연이는 캠퍼스에서 만날 수 있는 친구의 수를 알고 싶어한다. 캠퍼스는 ( N \times M ) 크기이며, 도연이는 빈 공간('O')과 사람('P')이 있는 곳으로 이동할 수 있다. 벽('X')은 이동할 수 없다. 도연이가 시작하는 위치는 'I'로 주어진다. 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성하는 문제이다.

입력

1. 첫 번째 줄에 캠퍼스의 크기를 나타내는 두 정수 ( N )과 ( M )이 주어진다.
2. 다음 ( N )개의 줄에 캠퍼스의 정보가 주어진다. 'O'는 빈 공간, 'X'는 벽, 'I'는 도연이의 시작 위치, 'P'는 사람이다.

출력

도연이가 만날 수 있는 사람의 수를 출력한다. 만약 아무도 만나지 못한 경우 "TT"를 출력한다.

 

 

풀이 설명

이 문제는 BFS(너비 우선 탐색)를 사용하여 도연이가 만날 수 있는 사람의 수를 세는 방식으로 해결할 수 있다.

from collections import deque
import sys
input = sys.stdin.readline

def bfs(x, y, graph, visited):
    queue = deque([(x, y)])
    visited[x][y] = True
    count = 0

    while queue:
        x, y = queue.popleft()
        for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                if graph[nx][ny] == 'P':
                    count += 1
                if graph[nx][ny] in ['P', 'O']:
                    visited[nx][ny] = True
                    queue.append((nx, ny))
    return count

N, M = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(N)]
visited = [[False] * M for _ in range(N)]

count = 0
for i in range(N):
    for j in range(M):
        if graph[i][j] == 'I':
            count = bfs(i, j, graph, visited)

if count > 0:
    print(count)
else:
    print("TT")

 

코드 설명

1. 입력 처리:
   • sys.stdin.readline을 사용하여 입력을 빠르게 처리한다.
   • 캠퍼스의 크기 ( N )과 ( M )을 입력받고, 캠퍼스 정보를 2차원 리스트 graph에 저장한다.
2. BFS 초기화:
   • visited 배열을 False로 초기화하여 모든 지점이 방문되지 않았음을 표시한다.
3. BFS 탐색:
   • 도연이의 시작 위치('I')를 찾아 BFS를 시작한다.
   • 큐를 사용하여 현재 위치에서 상하좌우 인접한 지점을 탐색한다.
   • 인접 지점이 사람('P')인 경우 count를 증가시키고, 빈 공간('O')이나 사람('P')인 경우 해당 지점을 큐에 추가하여 계속 탐색한다.
4. 결과 출력:
   • BFS 탐색이 끝난 후, count가 0보다 크면 만난 사람의 수를 출력하고, 그렇지 않으면 "TT"를 출력한다.

이 풀이 방식은 BFS를 사용하여 모든 지점을 탐색하므로, 도연이가 만날 수 있는 사람의 수를 효율적으로 계산할 수 있다.