토마토

풀이

 이전에 풀었던 백준 7576 토마토와 유사한 문제다. 유의할 점은 3차원 배열을 생성해서 6방향(앞,뒤,상,하,좌,우)을 탐색해줘야한다. 이전 문제 처럼 그래프를 돌면서 익은 토마토(1)를 찾아 queue에 넣는다. 그리고 BFS를 돌면서 앞,뒤,상,하,좌,우에 안 익은 토마토(0)가 있으면 graph[nx][ny] = graph[x][y] + 1을 통해 초기화해준다. 처음에 토마토에 1부터 +1씩 해주었기 때문에 마지막에 그래프에서 제일 큰 값에서 1을 뺀 값이 정답이 된다.

from collections import deque
import sys
M, N, H = map(int, input().split())
graph = []

queue = deque()

for i in range(H):
    t = []
    for j in range(N):
        t.append(list(map(int, sys.stdin.readline().split())))
        for k in range(M):
            if t[j][k] == 1:
                queue.append((i,j,k))
    graph.append(t)

dx = [1, -1, 0, 0, 0, 0]
dy = [0, 0, 1, -1, 0, 0]
dz = [0, 0, 0, 0, 1, -1]

while queue:
    z,y,x = queue.popleft()
    for i in range(6):
        nz = z + dz[i]
        ny = y + dy[i]
        nx = x + dx[i]
        if 0<=nz<H and 0<=ny<N and 0<=nx<M:
            if graph[nz][ny][nx] == 0:
                graph[nz][ny][nx] = graph[z][y][x] + 1
                queue.append((nz,ny,nx))
max_value = -10
for i in range(H):
    for j in range(N):
        max_value = max(max_value, max(graph[i][j]))
        for k in range(M):
            if graph[i][j][k] == 0:
                print(-1)
                exit(0)

print(max_value-1)

시간복잡도 : O(HNM)