[백준] 7569번 - 토마토 (DFS, BFS) - 결과 포함

www.acmicpc.net/problem/7569

7569번: 토마토

이전에 해결했었던 토마토 문제의 3차원 버전이다.

2021/01/31 - [개발 공부 (알고리즘)] - [백준] 7576번 - 토마토 (DFS, BFS) - 결과 포함

[백준] 7576번 - 토마토 (DFS, BFS) - 결과 포함

지금까지의 그래프 순회 (DFS, BFS) 문제들은 많아봤자 상, 하, 좌, 우 4가지 방향으로 움직였다.

그러나 이번 문제에서는 가로와 세로뿐만 아니라 높이까지 주어진다.

 

하지만 3차원이라고 해서 달라지는 것은 많지 않다.

단순하게 토마토가 익는 방향이 늘어났을 뿐이다.

한 정점에서 이동할 때, 상, 하, 좌, 우 4개의 방향에서 수직 방향으로 위, 아래 2개의 방향을 추가하기만 하면 된다.

 

6가지의 방향으로 전체를 순회하면서 토마토를 익히는데 가장 오래 걸리는 시간을 찾는다.

 

[소스코드]

from collections import deque
import sys

m, n, h = map(int, sys.stdin.readline().rstrip().split())

graph = [[] for i in range(h)]
queue = deque()

for i in range(h):
    for j in range(n):
        graph[i].append(list(map(int, sys.stdin.readline().rstrip().split())))

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

def bfs(x, y, z):
    for i in range(6):
        nx = x + dx[i]
        ny = y + dy[i]
        nz = z + dz[i]

        if nx < 0 or ny < 0 or nz < 0 or nx >= n or ny >= m or nz >= h:
            continue
        if graph[nz][nx][ny] == -1:
            continue
        if graph[nz][nx][ny] == 0:
            queue.append([nx, ny, nz])
            graph[nz][nx][ny] = graph[z][x][y] + 1


result = 0

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

while queue:
    x, y, z = queue.popleft()
    bfs(x, y, z)

resultList = []
for i in range(h):
    resultList.append(max(map(max, graph[i])))

maxResult = resultList[0]
for result in resultList:
    if maxResult < result:
        maxResult = result
result = maxResult - 1
for j in range(h):
    for i in range(n):
        if graph[j][i].count(0) > 0:
            result = -1
            break

print(result)