[Baekjoon/Python] 7569. 토마토 (BFS)
🍅 문제
3차원 상자에 토마토가 저장되어 있다.
- 익은 토마토: 1
- 익지 않은 토마토: 0
- 빈 칸: -1
익은 토마토는 하루가 지나면 상하좌우뿐만 아니라 위아래 방향까지 포함한 총 6방향으로 인접한 토마토를 익게 만든다.
모든 토마토가 익는데 걸리는 최소 일수를 구해야 하며,
모든 토마토가 익지 못하는 경우에는 -1을 출력한다.
풀이 과정
1) 문제 접근
이 문제는 단순 탐색 문제가 아니라 “최소 일수”를 구하는 문제이다.
또한 토마토가 동시에 퍼지기 때문에 순차 탐색이 아닌 BFS를 사용해야 한다.
특히 처음부터 익은 토마토가 여러 개 존재하므로, 모든 시작점을 큐에 넣는 다중 시작점 BFS가 필요하다.
2) BFS를 사용해야 하는 이유
DFS는 한 방향으로 깊게 탐색하기 때문에 최소 거리를 보장하지 못한다.
반면 BFS는 레벨 단위로 확장되므로, 각 토마토가 익는 시점이 곧 최소 일수가 된다.
3) 구현 핵심
- 처음 입력을 받을 때 익은 토마토(1)의 위치를 모두 큐에 넣는다.
- BFS를 진행하면서 인접한 토마토를 익힌다.
- 이때, 별도의 날짜 배열 없이 graph에 값을 누적한다.
🔥 나의 시행착오
1) 모든 좌표를 순회하며 처리하려 했던 문제
처음에는 3차원 배열을 모두 순회하면서 주변을 익히는 방식으로 접근하려 했다.
하지만 이 방법은 동시에 퍼지는 개념을 반영하지 못하고,
이미 같은 날 익어야 하는 토마토까지 순차적으로 처리되는 문제가 발생한다.
이 문제의 핵심은 “전파 + 최소 시간”이다.
이 조합은 BFS로 해결해야 한다.
2) days 변수로 최적화하려던 시도
전체 최댓값을 구하는 과정이 비효율적일 것 같아 days 변수를 따로 두고 graph의 값을 업데이트 할때마다 max()로 최댓값을 저장하려 했다.
하지만 실제로는 마지막에 한 번 전체를 순회하는 것은 시간복잡도에 큰 영향을 주지 않으며,
오히려 코드 복잡도와 실수 가능성만 증가시키는 요소였다.
최종 알고리즘
1) 입력을 받으며 초기 설정
익은 토마토의 위치를 모두 큐에 넣는다
2) BFS 수행
- 큐에서 하나씩 꺼낸다
- 6방향 탐색을 수행한다
- 익지 않은 토마토(0)를 만나면
→ 현재 값 + 1로 갱신
→ 큐에 추가
3) 결과 처리
- BFS 이후에도 0이 존재하면 → -1
- 그렇지 않으면 → 전체 최댓값 - 1 출력
💻 최종 코드
from collections import deque
import sys
input = sys.stdin.readline
M, N, H = map(int, input().split())
graph = []
queue = deque()
for h in range(H):
box = []
for n in range(N):
row = list(map(int, input().split()))
box.append(row)
for m in range(M):
if row[m] == 1:
queue.append((h, n, m))
graph.append(box)
# 6방향 (상, 하, 좌, 우, 위, 아래)
dh = [0, 0, 0, 0, -1, 1]
dn = [-1, 1, 0, 0, 0, 0]
dm = [0, 0, -1, 1, 0, 0]
while queue:
h, n, m = queue.popleft()
for i in range(6):
nh = h + dh[i]
nn = n + dn[i]
nm = m + dm[i]
if 0 <= nh < H and 0 <= nn < N and 0 <= nm < M:
if graph[nh][nn][nm] == 0:
graph[nh][nn][nm] = graph[h][n][m] + 1
queue.append((nh, nn, nm))
answer = 0
for h in range(H):
for n in range(N):
for m in range(M):
if graph[h][n][m] == 0:
print(-1)
sys.exit()
answer = max(answer, graph[h][n][m])
print(answer - 1)📚 배운점
1) 전파 + 최소 시간 → BFS로 접근한다
이 문제처럼 “퍼진다” + “최소 일수”가 같이 나오면 BFS를 먼저 떠올리는 것이 중요하다.
2) 다중 시작점 BFS를 기억하자
시작점이 여러 개인 경우, 처음부터 큐에 모두 넣고 시작해야 한다.
3) graph를 거리 배열로 활용할 수 있다
별도의 distance 배열 없이 값 자체를 증가시키는 방식으로 해결 가능하다.
4) 불필요한 최적화는 오히려 독이 된다
전체를 한 번 더 순회하는 비용보다, 코드 안정성과 정확성이 더 중요하다.
전체를 한 번 더 순회하는 것은 시간복잡도에 큰 영향을 미치지 않는다.
