아주 베이직한 bfs 문제이다. 왜 골드이지 싶은..?
먼저 익은 토마토가 존재하는 배열의 인덱스 좌표값을 큐에 모두 삽입한 후,
이들을 하나씩 popleft()하면서 상하좌우에 있는 값에 (자신의 값+1)을 더해주며 업데이트 하면 된다.
값이 -1인 경우는 토마토가 들어있지 않은 칸이다. 따라서 bfs()를 수행할 때 0이 아닌 값들에 대해서만 큐의 삽입 조건으로 본다. (0이 아니라는 뜻은 이미 익은 토마토이거나 토마토가 들어있지 않은 칸이므로)
전체 코드는 아래와 같다.
# from collections import deque
# import sys
# input = sys.stdin.readline
# m, n = map(int, input().strip().split())
# arr = []
# visited = [[0] * m for _ in range(n)]
# for _ in range(n):
# arr.append(list(map(int, input().strip().split())))
# d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# q = deque()
# for y in range(n):
# for x in range(m):
# if arr[y][x] == 1:
# q.append((y, x))
# visited[y][x] = 1
# elif arr[y][x] == -1:
# visited[y][x] = 1
# while q:
# y, x = q.popleft()
# for dy, dx in d:
# Y = dy + y
# X = dx + x
# if 0 <= Y < n and 0 <= X < m and not visited[Y][X]:
# arr[Y][X] = arr[y][x] + 1
# visited[Y][X] = 1
# q.append((Y, X))
# max = -2
# for y in range(n):
# for x in range(m):
# if arr[y][x] == 0:
# print(-1)
# exit()
# else:
# if max < arr[y][x]:
# max = arr[y][x]
# print(max - 1)
from collections import deque
import sys
input = sys.stdin.readline
m, n = map(int, input().strip().split())
arr = []
# visited = [[0] * m for _ in range(n)]
for _ in range(n):
arr.append(list(map(int, input().strip().split())))
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
q = deque()
for y in range(n):
for x in range(m):
if arr[y][x] == 1:
q.append((y, x))
# visited[y][x] = 1
elif arr[y][x] == -1:
pass
# visited[y][x] = 1
while q:
y, x = q.popleft()
for dy, dx in d:
Y = dy + y
X = dx + x
if 0 <= Y < n and 0 <= X < m and not arr[Y][X]:
arr[Y][X] = arr[y][x] + 1
q.append((Y, X))
max = -2
for y in range(n):
for x in range(m):
if arr[y][x] == 0:
print(-1)
exit()
else:
if max < arr[y][x]:
max = arr[y][x]
print(max - 1)