[Silver II] 헌내기는 친구가 필요해 - 21736 (BFS)

[Silver II] 헌내기는 친구가 필요해 - 21736

문제 링크

성능 요약

메모리: 134620 KB, 시간: 284 ms

분류

너비 우선 탐색(bfs), 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

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

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

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

입력

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

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

출력

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

풀이방법

1. 도연이(i) 좌표 찾기

2. 도연이를 기준으로 bfs 탐색

3. 빈 공간(O)이면 방문 체크(a) 후 계속 탐색

4. 사람(P)을 만나면 cnt 1씩 증가

5. cnt 출력!

 

느낀 점

처음에 bfs 탐색하는 함수를 사용하지 않고 도연이(i)를 찾으면 큐에 좌표를 넣어 상하좌우를 탐색했는데 실수로 for문에 i를 중복을 사용해버려서 어이없게 시간을 날렸다.. 맘편히 함수를 사용하자. (함수의 장점!)

#O는 빈 공간, X는 벽, I는 도연이, P는 사람이다
from collections import deque
n, m = map(int,input().split())
graph = []
dx, dy = (1,-1,0,0),(0,0,1,-1)
for i in range(n):
    graph.append(list(input()))
cnt = 0

def bfs(a,b):
    global cnt
    q = deque()
    q.append((a,b))
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = dx[i]+x, dy[i]+y
            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] != "X":
                if graph[nx][ny] == "O":
                    graph[nx][ny] = "a"
                    q.append((nx,ny))
                elif graph[nx][ny] == "P":
                    graph[nx][ny] = "a"
                    cnt += 1
                    q.append((nx,ny))

for i in range(n):
    for j in range(m):
        if graph[i][j] == "I":
            bfs(i,j)

if cnt == 0:
    print("TT")
else:
    print(cnt)