[백준/BOJ] - 7576번 python 풀이 - BFS

---

Key Point

1. 배열의 값이 1인 위치에서 동서남북으로 퍼지는 매커니즘이다.

2. 처음 입력받은 배열의 값이 1인 위치들을 모두 deque에 넣어준다.

3. 완성되어있는 deque속에 담겨진 위치를 토대로 bfs 를 동작시킨다.

4. 1일차에 익은 토마토에 의해 익혀진 토마토들의 값(배열 속 값)은 몇일 차 인지를 표시하기 위해 + 1 을 해준다.

5. bfs가 마무리 된 후 2중 for문을 돌리며 0인 값이 아직도 존재할 경우 -1 출력 존재하지 않을 경우 배열에 존재하는 최댓값 -1을 출력한다. 

---

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

m, n = map(int, input().split())
queue = deque([])
tomato = [list(map(int, input().split())) for _ in range(n)]
dx, dy = (-1, 1, 0, 0), (0, 0, -1, 1)

for i in range(n):
    for j in range(m):
        if tomato[i][j] == 1:
            queue.append((i, j)) #맨처음 익은 토마토들 queue에 다 넣어버리기

def bfs(): #동서남북 한번씩만 1로 만들고 끝내고 메인에서는
    while queue:
        x, y = queue.popleft()

        for i in range(4):
            rx = x + dx[i]
            ry = y + dy[i]

            if 0<= rx < n and 0<= ry < m:
                if tomato[rx][ry] == 0:
                    tomato[rx][ry] = tomato[x][y] + 1
                    queue.append((rx,ry))

bfs()
maxi = 0
for i in tomato:
    for item in i:
        if item == 0:
            print(-1)
            exit(0)
        maxi = max(maxi, item)
print(maxi-1)