[BOJ] 7569. 토마토

📌 문제 제목

문제 링크: BOJ 7569

---

🗒️ 문제 설명

보관 후 하루가 지나면 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.

며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램.

시간 제한: 1초

메모리 제한: 256MB

2 <= M, N <= 100

1 <= H <= 100

---

💡 문제 해결 아이디어

• 3중 for문을 돌며 토마토가 있는 좌표를 큐에 저장한다.
• 상하좌우위아래를 확인하며 익지 않은 토마토가 있으면 큐에 넣는다.
• 3중 for문을 돌며 익지 않은 토마토가 있는지 확인하면서 dist의 max값을 확인한다.

---

⌛️ 시간 복잡도

• O(H x N x M)

---

✅ 최종 코드

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

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

dist = [[[-1] * M for _ in range(N)] for _ in range(H)]
queue = deque([])
for k in range(H):
    for i in range(N):
        for j in range(M):
            if graph[k][i][j] == 1:
                queue.append((k, i, j))
                dist[k][i][j] = 0

direction = [(1, 0, 0), (-1, 0, 0), (0, 1, 0),
             (0, -1, 0), (0, 0, 1), (0, 0, -1)]


while queue:
    hp, xp, yp = queue.popleft()
    for nh, nx, ny in direction:
        dh, dx, dy = hp + nh, xp + nx, yp + ny
        if not (0 <= dh < H and 0 <= dx < N and 0 <= dy < M):
            continue
        if graph[dh][dx][dy] == 0 and dist[dh][dx][dy] == -1:
            queue.append((dh, dx, dy))
            dist[dh][dx][dy] = dist[hp][xp][yp] + 1

mx = 0
for k in range(H):
    for i in range(N):
        for j in range(M):
            if dist[k][i][j] == -1 and graph[k][i][j] == 0:
                print(-1)
                exit(0)
            mx = max(mx, dist[k][i][j])

print(mx)