백준 7569 토마토 (BFS, 3차원)

이번 문제는 저번 7576문제를 3차원으로 바꾼 문제이다.

https://guccin.tistory.com/92

백준 7576 토마토 (BFS, 행렬 그래프, python)

 

조건은 똑같다. 하루마다 양 사이드의 토마토가 익어가는데 추가되는 조건은 위아래 상자도 같이 적용된다는 것이다. 대충 3차원으로 생각해보고 위아래 같이 익게하는 조건을 추가하면 끝이다.

from collections import deque
m,n,h = map(int, input().split()) #열 행 상자수

q = deque([])
M = []
for x in range(h):
    tmp = []
    for y in range(n):
        tmp1 = list(map(int, input().split()))
        for z in range(m):
            if tmp1[z] == 1:
                q.append([x,y,z])
        tmp.append(tmp1)
    M.append(tmp)

def BFS():
    dx = [0,0,1,-1] # 동서남북
    dy = [1,-1,0,0]
    day = -1
    while q:
        day += 1
        for _ in range(len(q)):
            z,x,y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if (0<=nx<n) and (0<=ny<m) and (M[z][nx][ny]==0):
                    M[z][nx][ny] = 1
                    q.append([z,nx,ny])
            nz = z - 1
            if (0<=nz<h) and (M[nz][x][y]==0):
                M[nz][x][y] = 1
                q.append([nz, x,y])
            nz = z + 1
            if (0<=nz<h) and (M[nz][x][y]==0):
                M[nz][x][y] = 1
                q.append([nz, x,y])
    for z in range(h):
        for y in range(n):
            if 0 in M[z][y]:
                return -1
    return day 
print(BFS())