📌 문제 요약

• 문제 이름: 7576번: 토마토
• 알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색(BFS)
• 사용 언어: Python 3

$M \times N$ 크기의 상자에 토마토가 보관되어 있습니다. 1은 익은 토마토, 0은 익지 않은 토마토, -1은 빈 칸을 의미합니다. 익은 토마토의 상하좌우에 있는 익지 않은 토마토는 하루가 지나면 익게 됩니다. 토마토가 혼자 저절로 익는 경우는 없다고 할 때, 상자 안의 모든 토마토가 익을 때까지 걸리는 최소 일수를 구하는 문제입니다.

💡 문제 접근 방법 (핵심 로직)

이 문제는 최단 거리를 구하는 미로 탐색 문제와 유사하지만, 가장 큰 차이점은 시작점(익은 토마토)이 여러 개일 수 있다는 것입니다. 이를 해결하기 위해 '다중 시작점 BFS' 기법을 사용해야 합니다.

1. 시작점 일괄 큐(Queue) 삽입:
   만약 1을 발견할 때마다 개별적으로 BFS를 돌린다면, 동시다발적으로 토마토가 익어가는 상황을 제대로 시뮬레이션할 수 없고 시간 초과가 발생합니다. 따라서 bfs() 함수를 호출하기 전에, 이중 for문으로 상자를 훑으며 모든 1의 좌표를 먼저 queue에 담아두어야 합니다.
2. BFS를 통한 일수 누적 (In-place):
   큐에 담긴 토마토들을 하나씩 꺼내며 상하좌우를 탐색합니다. 익지 않은 토마토(0)를 발견하면, 해당 위치의 값을 graph[nx][ny] = graph[x][y] + 1 로 갱신합니다. 이렇게 하면 별도의 visited 배열 없이도 방문 처리가 될 뿐만 아니라, 며칠이 지났는지 자동으로 누적 기록됩니다.
3. 예외 처리 및 결과 도출:
   탐색이 끝난 후, 상자 배열을 다시 검사합니다.
   • 상자에 0이 하나라도 남아있다면 토마토가 모두 익지 못한 것이므로 -1을 출력합니다.
   • 모두 익었다면 배열의 최댓값을 구한 뒤, 첫날(익은 토마토)의 값이 1에서 시작했으므로 최댓값에서 1을 뺀 값이 실제 걸린 최소 일수가 됩니다.

💻 코드 구현

import sys
from collections import deque

input = sys.stdin.readline

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

queue = deque()

# 1. 맵 전체를 돌며 익은 토마토(1)를 모두 큐에 담기
for i in range(N):
    for j in range(M):
        if graph[i][j] == 1:
            queue.append((i, j))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
            
def bfs():
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 2. 범위를 벗어나지 않고, 안 익은 토마토(0)라면
            if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] == 0:
                queue.append((nx, ny))
                # 3. 일수 누적 기록
                graph[nx][ny] = graph[x][y] + 1

bfs()

result = 0

# 4. 탐색 종료 후 검증
for row in graph:
    # 안 익은 토마토가 존재하면 -1 출력 후 즉시 종료
    if 0 in row:
        print(-1)
        exit(0)
    # 가장 높은 값(가장 오래 걸린 일수) 갱신
    result = max(result, max(row))

# 시작이 1이었으므로 1을 빼서 출력
print(result - 1)

🚨 트러블 슈팅 및 회고

• 단일 시작점 vs 다중 시작점: 처음에는 미로 찾기 문제처럼 1을 찾으면 그 자리에서 바로 BFS를 시작하도록 구현하려다 멈칫했습니다. 그렇게 하면 첫 번째로 발견된 토마토가 맵 전체를 다 물들이고 난 뒤에야 두 번째 토마토의 순서가 오기 때문에 '동시에' 익어가는 최소 일수를 절대 구할 수 없습니다. BFS를 시작하기 전, 초깃값들을 큐에 전부 집어넣고 시작해야 큐의 특성(FIFO)에 의해 레벨(Level) 단위로 예쁘게 퍼져나간다는 큐와 BFS의 본질적인 원리를 체감했습니다.
• max 함수의 활용: 2차원 리스트에서 최댓값을 찾을 때 max(map(max, graph))와 같은 방식을 쓸 수도 있지만, 이 문제에서는 0이 포함되어 있는지 검사하는 과정이 무조건 필요하므로 for row in graph:를 돌면서 if 0 in row:로 검사하고 result = max(result, max(row))로 동시에 최댓값을 갱신하는 방식이 훨씬 효율적이고 직관적이었습니다.