[BOJ] 토마토

---

코드

from sys import stdin
from collections import deque
input = stdin.readline

dx = [0,0,1,-1]
dy = [1,-1,0,0]
queue = deque()

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

for i in range(N):
    for j in range(M):
        if graph[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 nx < 0 or nx >= N or ny < 0 or ny >= M:
            continue
        if graph[nx][ny] == -1:
            continue
        if graph[nx][ny] == 0:
            graph[nx][ny] = graph[x][y] + 1
            queue.append((nx, ny))

flag = True
for i in graph:
    for j in i:
        if j == 0:
            flag = False
            break

if flag:
    print(max(map(max, graph)) - 1)
else:
    print(-1)

결과

풀이 방법

• 인접한 좌표를 체크하면서 최단거리를 찾는 문제이므로 BFS를 활용하였다
• 처음부터 익어 있는 모든 토마토들로부터 인접한 덜 익은 토마토를 익게 하므로 큐에 익어 있는 모든 토마토들의 좌표를 추가한다
• 큐에서 좌표를 하나씩 꺼내면서 BFS를 수행하며 인접한 덜 익은 토마토들의 좌표에 (큐에서 꺼낸 좌표의 토마토가 익는 데 걸린 일수)+1 값을 저장한다
• 큐가 비었을 때 좌표에 덜 익은 토마토가 있는지 확인하고 없으면 좌표에서 최대값(모든 토마토가 익는 데 걸린 일수)를 구한다
• 처음 일수를 세기 시작한 좌표의 값이 1이었으므로 구한 최대값에서 1을 빼 주어야 한다

---