[백준] 7569번 토마토

💡문제접근

• 이전 포스팅에 있었던 [[백준] 7576번 토마토] 문제의 변형문제다. 기존의 문제는 2차원 배열에서의 상하좌우 형태를 탐색하는 전형적인 BFS 탐색 알고리즘의 문제였다면 이번 문제는 3차원 배열에서의 상하좌우와 위아래도 탐색을 해야하는 BFS 탐색 알고리즘의 문제였다.
• 조금 더디긴 했지만 접근 방식은 동일해 3차원으로의 확장이 제대로 이루어졌다면 더 빠르게 해결할 수 있는 문제였다.

• BFS 탐색 알고리즘을 이용하는 방법
  ①. BFS 함수 내에 queue를 만들어서 사용하는 방법
  ②. 바깥에 queue를 따로 만들고 BFS()의 매개변수를 넣지 않는 방법

💡코드(메모리 : 48576KB, 시간 : 1984ms)

from collections import deque
import sys
input = sys.stdin.readline

queue = deque()
M, N, H = map(int, input().strip().split())
tomato = []
for i in range(H):
    tmp = []
    for j in range(N):
        tmp.append(list(map(int, input().strip().split())))
        for k in range(M):
            if tmp[j][k] == 1:
                queue.append((i, j, k))
    tomato.append(tmp)

day = 0
def BFS():
    while queue:
        x, y, z = queue.popleft()
        dx = [0, 1, 0, -1, 0, 0]
        dy = [-1, 0, 1, 0, 0, 0]
        dz = [0, 0, 0, 0, 1, -1]
        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]
            if 0 <= nx < H and 0 <= ny < N and 0 <= nz < M and tomato[nx][ny][nz] == 0:
                queue.append((nx, ny, nz))
                tomato[nx][ny][nz] = tomato[x][y][z] + 1

BFS()
for i in tomato:
    for j in i:
        for k in j:
            if k == 0:
                print(-1)
                sys.exit(0)
        day = max(day, max(j))
print(day-1)

💡소요시간 : 20m