그래프를 탐색하되, bfs나 dfs처럼 연쇄적으로 탐색하지 말고 한 번에 근처에 있는 주변 노드들만 탐색한다.
연쇄적으로 한 번에 탐색하면 안 되는 이유는 총 탐색하는데 며칠이 걸리는지를 알아내야 하기 때문이다.
따라서 데크(deque)를 선언하고 인접한 노드를 데크에 추가하는 bfs의 방식을 활용하되, 데크에 새로 인접한 노드들을 추가하지는 않았다.
즉 한 번 bfs()를 실행할 때마다 익은 토마토 주변의 토마토만 익게 된다. bfs() 함수에서는 배열의 값이 0인 칸들만 1로 바꿔주는 것으로 이를 대신하였다.
배열의 값이 -1인 경우는 토마토가 없는 것이므로 인접한 토마토가 익는 효과가 나타나지 않는다. 그러므로 배열의 값이 꼭 0일 때만 1로 만들어 주어야 한다.
ripe_list라는 변수를 선언해서 맨 처음에 익어 있는 토마토를 해당 변수에 추가한다.
이후에는 bfs()를 실행하면서 맨 처음에 익어 있는 토마토에 의해 새로 익게 된 토마토만 ripe_list 변수에 추가해 준다.
이런 방식으로 while 문을 실행하면서, 새로 익게 되는 토마토가 없는 경우 탐색을 종료한다.
while 문에서는 day 값을 1씩 늘려가면서 탐색한다. 이때 day 값을 0으로 하면 0번째 값을 탐색할 때에도 day 값이 1씩 추가되기 때문에, day 값을 -1로 두고 시작한다.
새로 익게 되는 토마토가 없는 경우, 즉 ripe_list의 값이 없는 경우 while 문을 빠져나오고 난 뒤에는 전체 배열을 순회하면서 값이 0인 칸을 탐색한다.
만약 값이 0인 칸이 있다면 익지 않은 토마토가 있다는 뜻이므로 토마토가 모두 익지 못한 것이다. 이 경우에는 -1을 출력하고, 나머지 경우에는 while문으로 값을 증가시킨 day 값을 출력한다.
import sys
from collections import deque
input = sys.stdin.readline
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
def bfs(ripe):
Q = deque(ripe)
new_ripe = []
while Q:
x, y = Q.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if nx >= N or nx < 0 or ny >= M or ny < 0:
continue
if arr[nx][ny] == 0:
arr[nx][ny] = 1
new_ripe.append([nx, ny])
return new_ripe
M, N = map(int, input().split())
arr = []
for _ in range(N):
arr.append(list(map(int, input().split())))
ripe_list = []
for i in range(N):
for j in range(M):
if arr[i][j] == 1:
ripe_list.append([i, j])
day = -1
while ripe_list:
ripe_list = bfs(ripe_list)
day += 1
ripe = True
for i in range(N):
for j in range(M):
if arr[i][j] == 0:
ripe = False
break
if not ripe:
print(-1)
else:
print(day)
