7576번 토마토(python3)

https://www.acmicpc.net/problem/7576

7576번: 토마토

우선 토마토가 있는 곳(1인 곳)을 visited 리스트에서 1로 해주고 queue에 append 해준다. 그리고 bfs를 적용해주는데 이때 새로 update되는 visited에는 이전 visited에서 +1 해준 값을 넣어준다. 그리고 visited 배열에서 가장 큰 값을 출력해주면 답이 된다.

from collections import deque

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

M, N = map(int, input().split())
tomato = []

for i in range(N):
    tomato.append(list(map(int, input().split())))

visited = [[0] * M for _ in range(N)]
queue = deque()
for i in range(N):
    for j in range(M):
        if tomato[i][j] == 1:
            visited[i][j] = 1
            queue.append([i, j])
while queue:
    x, y = queue.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < M:
            if visited[nx][ny] == 0 and tomato[nx][ny] == 0:
                queue.append([nx, ny])
                visited[nx][ny] = visited[x][y] + 1
                tomato[nx][ny] = 1


ans = 0
flag = False
for i in range(N):
    for j in range(M):
        if tomato[i][j] == 0:
            ans = -1
            flag = True
            break
        if visited[i][j] > ans:
            ans = visited[i][j]
    if flag:
        break
if ans == -1:
    print(-1)
else:
    print(ans - 1)