문제 출처

문제 유형

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

해당 문제는 solved.ac 사이트 기준 실버 2 문제입니다.

N x M 크기의 테이블에서 상하좌우로 이동하면서 특정 조건에 따른 카운트를 출력하는 문제입니다.

• (x, y)에 있다면 이동할 수 있는 곳은 (x+1, y), (x, y+1), (x-1, y), (x, y-1)이다.

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

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

무난한 상하좌우 그래프 탐색 연습문제입니다. BFS/DFS 둘 다 쓸 수 있으며, 저는 BFS를 사용해서 해결했습니다. N과 M의 최대크기가 작기 때문에 재귀함수로도 해결할 수 있어 보입니다.

또한, 시간복잡도를 줄이기 위해서 deque()를 사용했습니다.

풀이 코드

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

n, m = map(int, input().split())

visited = [[False] * m for _ in range(n)]
numArr = [[] for _ in range(n)]
start = [-1, -1]

def bfs():
    queue = deque()
    queue.append([start[0], start[1]])
    visited[start[0]][start[1]] = True

    answer = 0

    while queue:
        x, y = queue.popleft()

        for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
            if 0 <= nx < n and 0 <= ny < m and numArr[nx][ny] != 'X' and not visited[nx][ny]:
                visited[nx][ny] = True
                queue.append([nx, ny])

                if numArr[nx][ny] == 'P':
                    answer += 1

    return ['TT', answer] [answer > 0]

for i in range(n):
    numArr[i] = [*input()]
    for j in range(m):
        if numArr[i][j] == 'I':
            start[0], start[1] = i, j

print(bfs())