[Python] 백준 #7576 토마토 - bfs

문제

7576번: 토마토

풀이

#2178 미로탐색(https://yuuj.tistory.com/85)과 유사한 문제

import sys
from collections import deque

M, N = map(int, sys.stdin.readline().split(" "))
box = []

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

for _ in range(N):
    box.append(list(map(int, sys.stdin.readline().split(" "))))

queue = deque()

# 초기 토마토 위치 넣기
for i in range(N):
    for j in range(M):
        if box[i][j] == 1:
            queue.append([i, j])

while queue:
    i, j = queue.popleft()

    for k in range(4):
        ndr = i + dr[k]
        ndc = j + dc[k]

        if 0 <= ndr < N and 0 <= ndc < M and box[ndr][ndc] == 0:
            queue.append([ndr, ndc])
            box[ndr][ndc] = box[i][j] + 1

max = -1
flag = 0
for i in range(N):
    for j in range(M):

        if box[i][j] > max:
            max = box[i][j]
        if box[i][j] == 0:
            max = 0
            flag = 1
            break
    if flag == 1:
        break

print(max-1)