백준 7576번 - 토마토

토마토 문제 바로 가기

풀이 날짜: 2026-01-05

baekjoon 알고리즘 문제 풀이

풀이 코드


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

dx = [0,0,-1,1]
dy = [-1,1,0,0]

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

visited = [[False]*m for _ in range(n)]

q = deque()
for y in range(n):
    for x in range(m):
        if graph[y][x] ==  1:
            q.append((x,y))
            visited[y][x] = True

def bfs():
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0<=ny<n and 0<=nx<m and not visited[ny][nx] and graph[ny][nx] == 0:
                visited[ny][nx] = True
                graph[ny][nx] = graph[y][x]+1
                q.append((nx,ny))
bfs()
answer = 0
for y in range(n):
    for x in range(m):
        if graph[y][x] == 0:
            print(-1)
            sys.exit(0)
        answer = max(answer, graph[y][x])
print(answer-1)

문제 핵심 요약:

1 : 익은 토마토 (출발점)
0 : 안 익은 토마토
-1 : 토마토가 없는 칸

익은 토마토는 상하좌우로 하루 뒤에 주변 토마토를 익게 만든다.
즉, “며칠 후에 익는지”가 거리(시간)처럼 증가한다.

내가 선택한 풀이 방식: BFS

이 문제의 특징은 시작점이 1개가 아니라는 점이다.

처음부터 익은 토마토(1)가 여러 개 있을 수 있다.
이 토마토들이 동시에 퍼져나가야 ‘최소 일수’가 된다.

따라서 BFS 큐에 처음부터 익은 토마토들을 전부 넣고 시작했다.

큐에는 “현재 시점에 퍼질 위치들”이 들어가고, pop 순서가 날짜(단계)를 보장한다

BFS에서 큐는 “다음에 처리할 칸들”을 순서대로 담는다.
처음에는 0일차(처음부터 익은 토마토들)만 들어 있고, 그 다음에 1일차에 익는 칸들이, 그 다음에 2일차…
이런 식으로 층(layer)이 자동으로 만들어진다.
그래서 popleft()로 꺼낼 때마다 그 칸은 “그 시점에 익은 칸”이며, 인접 칸을 +1로 업데이트하면 “하루 뒤에 익는다”라는 규칙이 자연스럽게 코드에 반영된다.

멀티 소스 BFS 템플릿(초기 큐 세팅)이 정답을 좌우한다

이 문제에서 중요했던 건, “출발점이 여러 개면 전부 큐에 넣고 시작한다”는 것이었다.
한 개만 넣으면 실제로는 동시에 전파되어야 할 것들을 순차적으로 처리하게 되기 때문에 오류가 발생한다.
따라서 for y, for x로 graph[y][x]==1인 모든 좌표를 찾아서 q.append((x,y)) 하는 초기 세팅이 중요하다는 것을 기억하자.

어려웠던 점

answer - 1이 왜 필요한지(시작값 보정)가 직관적이지 않았다

처음부터 익은 토마토가 0일차인데 배열에는 1로 들어오기 때문에, BFS 확산 날짜를 저장할 때도 2,3,4…으로 커진다.
따라서 최댓값이 실제 날짜보다 1 크게 나오므로, 마지막에 -1을 해줘야 한다.

Vienna sausage