[BaekJoon Online Judge] 7569 – 토마토

문제

https://www.acmicpc.net/problem/7576

소스코드

7576 문제에서 공간 차원이 하나 늘어난 문제. 7576 문제와 마찬가지로 bfs를 이용한 최단거리 문제로 해결할 수 있다.

from collections import deque

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

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

q = deque()
for i in range(H):
    for j in range(N):
        for k in range(M):
            if field[i][j][k] == 1:
                q.append((i,j,k))
                visit[i][j][k] = 0

while q:
    z,x,y = q.popleft()
    for i in range(6):
        to_z,to_x,to_y = z+dz[i],x+dx[i],y+dy[i]
        if to_z>=0 and to_x>=0 and to_y>=0 and to_z<H and to_x<N and to_y<M:
            if field[to_z][to_x][to_y] == 0 and visit[to_z][to_x][to_y] == 0:
                q.append((to_z,to_x,to_y))
                visit[to_z][to_x][to_y] = visit[z][x][y] + 1

ripe = True
for i in range(H):
    for j in range(N):
        for k in range(M):
            if field[i][j][k] == 0 and visit[i][j][k] == 0:
                ripe = False
                break

if ripe:
    ans = 0
    for i in range(H):
        for j in range(N):
            for k in range(M):
                if ans < visit[i][j][k]:
                    ans = visit[i][j][k]
    print(ans)
else:
    print(-1)