🍅 백준 7569번:토마토 (BFS 활용)

---

🧐 문제 해석

• M*N 크기의 총 H층으로 쌓여있는 토마토 박스가 있다.
• 각 칸에는 토마토가 담겨 있을 수도 없을 수도 있고 익은, 익지 않은 토마토가 섞여있다.
• 익은 토마토랑 붙어있는(동서남북상하) 토마토는 하루가 지나면 익는다

🎯 목표:

토마토가 모두 익을 수 있다면 익는데 걸린 날짜를, 익지 못한다면 -1, 이미 전부 익었다면 0을 출력해라

---

🔍 핵심 아이디어

이 문제는 **정답(날짜 및 익힘여부)**를 BFS로 찾는 그래프 탐색 문제이다.

✅ BFS 용도

• 토마토 익히기
• 날짜 계산하기

---

🍅 토마토가 전부 익어있나 ?

is_rippen = False
for k in range(h):
    for i in range(m):
        for j in range(n):
            if tomato[k][i][j] == 1 :
                visited[k][i][j] = True
                queue.append((k,i,j))
            if tomato[k][i][j] == 0 :
                is_rippen = True

• 토마토가 전부 익혀있는지 아닌지를 확인하기 위한 boolean 변수 선언
• 익지 않은 상태에 토마토가 한개도 없다면 True 처리가 안됨
• True면 0을 출력하고 함수 종료

📅 토마토는 전부 익는데 얼마나 걸리는가?

while queue :
    now_z, now_y, now_x = queue.popleft()
    for i in range(6):
        next_z = now_z + dz[i]
        next_y= now_y + dy[i]
        next_x = now_x + dx[i]
        if 0<=next_z<h and 0<=next_y<m and 0<=next_x<n :
            if not visited[next_z][next_y][next_x] :
                if tomato[next_z][next_y][next_x] == 0:
                    visited[next_z][next_y][next_x] = True
                    tomato[next_z][next_y][next_x] = tomato[now_z][now_y][now_x] + 1
                    queue.append((next_z,next_y,next_x))

• 3차원 배열을 입력받을때 익은 토마토를 큐에 append 해놓음
• 방문 처리로 이미 익힌 토마토는 방문하지 않도록 예방
• 토마토가 익을때 현재 자리에 적혀있는 숫자보다 + 1 숫자를 기록함으로써 다른날 익은 토마토를 구분한다.
• 마지막에 배열에 저장된 가장 큰 숫자를 출력하면 그것이 날짜를 의미한다.

---

💯 정답

import sys
from collections import deque

n, m , h = map(int,input().split())
tomato = []
# print(arr[1][1][2])
# 층, 행, 열
dx = [-1,1,0,0,0,0]
dy = [0,0,-1,1,0,0]
dz = [0,0,0,0,-1,1]
visited = [[[False for _ in range(n)] for _ in range(m)] for _ in range(h)]

queue = deque()

for _ in range(h):
    layer = []
    for _ in range(m):
        row = list(map(int, input().split()))
        layer.append(row)
    tomato.append(layer)

is_rippen = False
for k in range(h):
    for i in range(m):
        for j in range(n):
            if tomato[k][i][j] == 1 :
                visited[k][i][j] = True
                queue.append((k,i,j))
            if tomato[k][i][j] == 0 :
                is_rippen = True

if not is_rippen :
    print(0)
    sys.exit()

while queue :
    now_z, now_y, now_x = queue.popleft()
    for i in range(6):
        next_z = now_z + dz[i]
        next_y= now_y + dy[i]
        next_x = now_x + dx[i]
        if 0<=next_z<h and 0<=next_y<m and 0<=next_x<n :
            if not visited[next_z][next_y][next_x] :
                if tomato[next_z][next_y][next_x] == 0:
                    visited[next_z][next_y][next_x] = True
                    tomato[next_z][next_y][next_x] = tomato[now_z][now_y][now_x] + 1
                    queue.append((next_z,next_y,next_x))




has_zero = any(0 in row for layer in tomato for row in layer)
if has_zero :
    print(-1)
else :
    max_day = max(max(max(row) for row in layer) for layer in tomato)
    print(max_day - 1)

---

💭 생각

✅ 결론 한 줄

이 문제는 BFS를 통해 상태가 변화하는 과정을 "단계별(날짜)"로 추적하는 전형적인 시뮬레이션 문제다! 🍅

---

🔑 자꾸 헷갈리는 BFS 사용

BFS에서는 보통 DFS처럼 함수 인자로 깊이(혹은 날짜, 거리 등 상태)를 넘기지 않는다. 대신 큐에 들어가는 값 자체에 그 상태(단계)를 같이 저장하거나, 혹은 탐색 대상 배열 자체에 날짜나 거리 정보를 덮어써서 기록하는 방식으로 단계 구분을 해야 하는 것 같다.

예를 들어, 토마토 문제에선 tomato[z][y][x] 배열에다가 그냥 날짜를 적어버리는 식으로 변화하는 날짜를 기록하고 상태 변화 또한 기록한다.

이렇게 BFS는 큐에서 하나씩 꺼낼 때마다 그 상태의 변화(날짜/거리/단계 등)가 이미 배열에 누적되거나, 큐에 함께 들어가 있거나 해서 별도로 재귀적으로 넘기지 않고 문제를 해결해 나가는 식이다.

정리하자면, BFS에선 함수 인자 없이도 큐의 순서와 배열 기록만으로도 “단계적 변화”가 가능한 구조이기 때문에, 날짜나 거리 같은 걸 따로 넘길 필요가 없고, 배열 자체가 기록지가 된다는 거..이게 아직은 너무 어렵다.. 😮‍💨 🥺