[BOJ] 7569: 토마토(Python)

7569번: 토마토

문제 설명

토마토 상자를 수직으로 쌓아 올려 보관한다. 익은 토마토는 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향의 익지 않은 토마토를 익게 할 수 있다. 토마토가 익는 데 하루가 걸린다고 할 때, 모든 토마토가 익을 때까지 최소 며칠이 걸리는지 구해보자.

나의 풀이

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

def func():
    m,n,h=map(int,input().split())
    box=[[list(map(int,input().split())) for _ in range(n)] for _ in range(h)]
    d=[(0,0,1),(0,0,-1),(0,1,0),(0,-1,0),(1,0,0),(-1,0,0)]
    q=deque()

    for i in range(h):
        for j in range(n):
            for k in range(m):
                if box[i][j][k]==1:
                    q.append([i,j,k])

    while q:
        z,y,x=q.popleft() # x-m, y-n, z-h
        for dx,dy,dz in d:
            nx,ny,nz=dx+x,dy+y,dz+z
            if 0<=nx<m and 0<=ny<n and 0<=nz<h:
                if box[nz][ny][nx]==0:
                    box[nz][ny][nx]=box[z][y][x]+1
                    q.append([nz,ny,nx])
    
    day=0
    for i in range(h):
        for j in range(n):
            for k in range(m):
                if box[i][j][k]==0:
                    return -1
                day=max(day,box[i][j][k])
    return day-1
    
print(func())

3차원 배열에 대한 BFS를 수행한다.

시간복잡도

상자의 가로, 세로가 100, 상자의 개수도 100이므로 O(10^6)이다.