백준은 bfs 문제인 토마토 이름의 문제가 두개있다. 이 글은 그중 두번째 토마토 문제인 3차원 bfs 문제를 다룹니다.

❓ Problem

🤔 How

1. 기존 토마토 문제처럼 토마토가 익는데는 주변에 익은 토마토 여부가 필요하다.
2. 구해야하는건 토마토가 모두익는데의 최소시간 이다.
3. 토마토가 모두 익지 않았다면 -1 을 출력해야한다.
4. 기존 토마토문제와는 다르게 3차원 토마토문제이다. 상하좌우 z축의 위아래인 총 6방향으로 이동한다.

❗ Solve

+# 토마토
import sys
from collections import deque
input = sys.stdin.readline
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())
visited = [[[False for _ in range(M)] for y in range(N)] for z in range(H)]

# for z in range(H):
#     for y in range(N):
#         print(visited[z][y])

board = []
for _ in range(H):
    floor = []
    for _ in range(N):
        floor.append(list(map(int, input().split())))
    board.append(floor)


def find_tomato(board, visited):
    tomatoes = []  # xyz
    for z in range(H):
        for y in range(N):
            for x in range(M):
                if board[z][y][x] == 1:
                    tomatoes.append([x, y, z, 0])
                    visited[z][y][x] = True
                elif board[z][y][x] == -1:
                    visited[z][y][x] = True
    return tomatoes


def check_visited(visited):
    for z in range(H):
        for y in range(N):
            if False in visited[z][y]:
                return True
    return False


def bfs(board, visited):
    preset_tomatoes = find_tomato(board, visited)
    q = deque(preset_tomatoes)
    answer = 0
    while q:
        x, y, z, depth = q.popleft()
        if depth > answer:
            answer = depth
        for i in range(6):
            nx, ny, nz = x+dx[i], y+dy[i], z+dz[i]
            if 0 <= nx < M and 0 <= ny < N and 0 <= nz < H and not visited[nz][ny][nx]:
                visited[nz][ny][nx] = True
                q.append([nx, ny, nz, depth+1])
    if check_visited(visited):
        return -1
    return answer


print(bfs(board, visited))