[Graph] 토마토

from collections import deque

M, N = map(int, input().split())
tomato = [list(map(int, input().split())) for _ in range(N)]

direction = {0: (0, 1), 1: (0, -1), 2: (1, 0), 3: (-1, 0)}
flag = False

def BFS():
    q = deque()

    for i in range(N):
        for j in range(M):
            if tomato[i][j]==0: flag = True
            if tomato[i][j]==1: q.append((i, j))

    while q:
        x, y = q.popleft()
        for i in range(4):
            x2, y2 = x+direction[i][0], y+direction[i][1]
            if 0<=x2<N and 0<=y2<M and tomato[x2][y2]==0:
                tomato[x2][y2] = tomato[x][y] + 1
                q.append((x2, y2))

BFS()

if 0 in [tomato[a][b] for a in range(N) for b in range(M)]:
    days = -1
else:
    if not flag: days = 0
    days = max([tomato[a][b] for a in range(N) for b in range(M)]) - 1

print(days)

토마토가 보관된 위치 2차원 배열으로 표현
인접한 토마토가 모두 익는 데 걸리는 최소 날짜 수를 구하는 문제 -> BFS
전에 풀었던 문제를 참고하여 위쪽 아래쪽 오른쪽 왼쪽 방향으로 이동하는 경우를 계산
flag를 사용해서 처음 tomato 배열에 0이 있었는지 확인하고 처음부터 없었고 지금도 없는 상태라면 토마토가 모두 익지 못하는 상황이므로 -1 출력