백준 - 토마토 / Gold 5 / 7569번 / Python

문제 📋

백준 - 토마토

풀이 📝

import sys
from collections import deque


def solution(n, m, h, storage):
    day = 0
    unripe_cnt = 0
    q = deque()
    delta = [
        (1, 0, 0), (-1, 0, 0), (0, 1, 0),
        (0, -1, 0), (0, 0, 1), (0, 0, -1)
    ]

    for i in range(h):
        for j in range(m):
            for k in range(n):
                if storage[i][j][k] == 1:
                    q.append((i, j, k))
                elif storage[i][j][k] == 0:
                    unripe_cnt += 1

    if unripe_cnt == 0:
        return day

    while q:
        for _ in range(len(q)):
            height, row, col = q.popleft()

            for delta_h, delta_row, delta_col in delta:
                new_height = height + delta_h
                new_row = row + delta_row
                new_col = col + delta_col

                if new_height < 0 or new_height >= h or new_row < 0 or new_row >= m or new_col < 0 or new_col >= n:
                    continue
                if storage[new_height][new_row][new_col] == 0:
                    q.append((new_height, new_row, new_col))
                    storage[new_height][new_row][new_col] = 1
                    unripe_cnt -= 1
        if q:
            day += 1

    if unripe_cnt > 0:
        return -1

    return day


n, m, h = map(int, sys.stdin.readline().split())
storage = []

for _ in range(h):
    storage.append([list(map(int, sys.stdin.readline().split())) for _ in range(m)])

print(solution(n, m, h, storage))

3차원 공간에서 익은 토마토와 안익은 토마토가 있고
익은 것으로 부터 주위로 퍼져나갈 때 모든 토마토가 익는 최소시간을 구하는 문제이다.

최소시간을 찾는 것이기 때문에 바로 BFS를 떠올렸고
3차원 공간을 여섯방향으로 BFS 탐색하면서 하나의 breadth를 탐색할 때 마다
day를 1씩 증가 시켜주었다.