[백준] 7569번: 토마토

문제

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

7569번: 토마토

 

풀이

BFS(너비 우선 탐색)를 사용해 풀었습니다.

1. 6 방향(위, 아래, 상, 우, 하, 좌)을 미리 설정해 줍니다.
2. 익은 토마토(1)의 위치를 모두 큐에 추가합니다.
3. 익은 토마토를 주변으로 6 방향을 확인하며 익지 않은 토마토(0)를 익은 토마토(1)로 바꿔주고 바뀐 토마토 위치를 큐에 추가합니다.
4. 시작 시점에 있던 큐를 모두 수행하면 하루가 지난 것이므로 L에 1을 더합니다.
5. 마지막으로 익지 않은 토마토가 존재한다면 -1을, 모두 익었다면 L을 출력합니다.

 

코드

파이썬

import sys
from collections import deque

input = sys.stdin.readline

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

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


def BFS():
    L = -1
    queue = deque()
    for i in range(H):
        for j in range(N):
            for k in range(M):
                if boxes[i][j][k] == 1:
                    queue.append((i, j, k))
    while queue:
        for _ in range(len(queue)):
            x, y, z = queue.popleft()
            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 boxes[nx][ny][nz] == 0
                ):
                    boxes[nx][ny][nz] = 1
                    queue.append((nx, ny, nz))
        L += 1
    for i in range(H):
        for j in range(N):
            for k in range(M):
                if boxes[i][j][k] == 0:
                    return -1
    return L


print(BFS())