백준 7576

m X n 상자에 들어있는 토마토의 상태(-1 또는 0 또는 1)가 주어질 때,
모든 토마토가 익게 되는 최소 일수를 구하는 문제이다.

아직 익지 않은 토마토는,
본인의 상하좌우에 있는 익은 토마토에 의해서만 익을 수 있다.

아래와 같이 BFS로 접근했다.

1) 익은 토마토의 좌표를 q(queue)에 넣는다.
2) 각 좌표의 상하좌우에 익지 않은 토마토가 있다면 익힌다.
3) 이때, 자신을 익혀준 토마토의 값에 1을 더한 값을 자신의 좌표에 저장한다.
4) 이는 자신이 익혀지게까지 소요된 날짜 + 1일을 의미한다.
5) q가 빌 때까지 위의 과정을 반복한다.
6) graph에 저장된 최댓값 또는 -1(0이 하나라도 존재하는 경우)이 정답이 된다.

정답(코드)은 다음과 같다.

# 7576

import sys
from collections import deque

# 입력
m, n = map(int, sys.stdin.readline().split())

graph = []
for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))

# q: 익은 토마토 좌표
q = deque([])
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            q.append([i, j])

# bfs
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
while q:
    x, y = q.popleft()

    for i in range(4):
        # 탐색하려는 좌표
        nx = x + dx[i]
        ny = y + dy[i]

        # 범위 검토
        if 0 <= nx < n and 0 <= ny < m:
            if graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] + 1
                q.append([nx, ny])

ans = 0
for line in graph:
    for tomato in line:
        if tomato == 0:
            print(-1)
            exit()

    ans = max(ans, max(line))

print(ans - 1)