[BOJ / 백준 7576번][PYTHON] 토마토 - (BFS)

 

간단히 정리하면, 익은 토마토와 익지 않은 토마토에 대한 정보가 주어지는데 익는 것이 퍼진다는 것이다. (질병처럼)

그래서 얼마나 지나면 다 퍼지냐? 이것을 물어보았다.

 

해당 문제는 대표적인 BFS 문제 중 하나이다. 다 풀고 나서 생각해보면 문제가 굉장히 직관적이다. 다음으로 어디로 갈 것인지가 굉장히 명확히 정해져 있다(인접한 곳). 그냥 count로 며칠이 지났는 지를 세고, bfs의 큐를 통해서 다음 갈 곳을 정하고 다음 갈 곳들을 count 변수를 통해서 값을 update 시키면 마지막 토마토가 물드는 순간에 (전부 다 익는다는 가정 하에) 마지막 토마토에 count가 아름답게 딱 적혀있을 것이다.

 

그렇다면 BFS는 도대체 뭐길래 글쓰는 놈은 신나서 나불대고 있는 것일까

BFS는 DFS와 비슷한 탐색 기법이며 너비 우선? 깊이 우선? 중에서 너비 우선에 해당하는 방법이다.

단순하게 정말 직관적으로 생각하면 된다.

 

비유하여 설명한다면,

1. 할머니께서 아끼시는 도자기가 있으신데 그것을 누군가가 깨버렸다.

2. 할머니께선 아들이 둘 있고, 그 아들은 각각 2명의 자식이 있다.

3. 이때 (편의를 위해 큰 아들, 작은 아들이라 할 때) 분노하신 할머니께서 큰 아들을 터시고 작은 아들을 터신다면 BFS이다.

4. 이때 큰 아들을 터시고 큰 아들의 자식인 손주들을 터시기 시작하신다면 이것은 DFS이다. (큰 아들의 집안을 먼저 터는 것)

 

이 두 방식인 DFS와 BFS는 구현의 차이가 존재한다. DFS는 보통 재귀의 방식으로 깊게 들어가며, 

BFS는 반복문인 while이나 for문을 이용하여 다음 깊이로 내려가며 너비로의 이동은 큐를 이용하여 인접한 노드로 이동한다.

큐에 들어가는 조건 자체가 "나 지금 어디로 이동할 것인가" 이것을 계속 찾고 다음 도착지를 추가해주는 것이다.

 

from collections import deque

m, n = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

q = deque([])
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
count = 0

for i in range(n):
    for j in range(m):
        if arr[i][j] == 1:
            q.append([i, j])

def bfs():
    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 arr[nx][ny] == 0:
                arr[nx][ny] = arr[x][y] + 1
                q.append([nx, ny])

bfs()
for i in arr:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
    count = max(count, max(i))
print(count - 1)

구현 방식은 다음과 같다. 여기서 복잡해 보이지만, 실제 구현 자체는 설명한 것과 크게 다르지 않다.

여기서 dx, dy로 배열을 만들었는데 이 부분이 아까 설명한 것과 같은 "다음에 이동할 곳"이다.

인접이라는 것은 2차원 배열에서 동서남북 밖에 없기 때문에 그것을 직관적으로 구현한 것이다.

 

이렇게 맞았다.