백준 / 7576 / 토마토 (bfs)

from collections import deque

direction = [[1,0], [-1,0],[0,1],[0,-1]]

m, n = [int(v) for v in input().split()]
maps = [[0] * m for _ in range(n)]

for i in range(n):
    maps[i] = list(map(int, input().split()))

q = deque()

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

result = 0
while q:
    x, y = q.popleft()

    for d in direction:
        nx, ny = x+d[0], y+d[1]

        if 0<=nx<n and 0<=ny<m and maps[nx][ny] == 0:
            maps[nx][ny] = maps[x][y] + 1
            result = max(result, maps[nx][ny])
            q.append([nx,ny])

flag = 0
for i in range(n):
    if 0 in maps[i]:
        print(-1)
        break
    if maps[i].count(1) + maps[i].count(-1) == m:
        flag += 1
else:
    if flag == n:
        print(0)
    else:
        print(result-1)

시작점이 여러개인 bfs 문제

처음 deque에 1인 시작점을 모두 입력한 후 bfs 진행한다.
이 점만 고려하면 일반적인 bfs 문제와 똑같다.

하나 더 주의 할 점은 처음부터 모든 토마토가 익어있는 상태라면 즉 1 혹은 -1, 1 로만 채워져있다면 이 경우 0을 출력해야한다.

마지막 for 문에서 0이 있는 경우와 1, -1 로만 채워진 경우데 대해서 check해 준다.