[백준] 7569: 토마토

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

 

from collections import deque
import sys
def solution():
    m, n, h = map(int, sys.stdin.readline().split())
    dx = [ 0, 0, -1, 1, 0, 0 ] # 세로 # 6방향 이동 (좌우, 상하, 위아래)
    dy = [ -1, 1, 0, 0, 0, 0 ] # 가로
    dz = [ 0, 0, 0, 0, -1, 1 ] # 층
    q = deque()
    tomato = []
    for z in range(h):
        layer = []
        for x in range(n):
            row = list(map(int, sys.stdin.readline().split()))
            for y in range(m):
                if row[y] == 1: # 익은 토마토 위치가 랜덤이기 때문에 위치를 큐에 저장
                    q.append([z, x, y])
            layer.append(row)
        tomato.append(layer)
    def bfs():
        while q:
            z, x, y = q.popleft()
            for i in range(6):
                nz, nx, ny = z + dz[i], x + dx[i], y + dy[i]
                if 0 <= nz < h and 0 <= nx < n and 0 <= ny < m:
                    if tomato[nz][nx][ny] == 0: # 익지 않은 토마토
                        tomato[nz][nx][ny] = tomato[z][x][y] + 1 # 날짜 증가
                        q.append([nz, nx, ny])
    bfs()
    max_days = 0
    for z in range(h):
        for x in range(n):
            for y in range(m):
                if tomato[z][x][y] == 0: # 익지 않은 토마토가 남아 있으면
                    return -1
                max_days = max(max_days, tomato[z][x][y]) # if에 걸리지 않으면 최댓값 갱신
    return max_days-1 # 최초 익은 토마토가 1부터 시작했으므로 -1 해줘야 정확한 값
print(solution())

최단경로찾기 문제입니다.

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