[BOJ] 백준 7569 토마토 / BFS

이미지를 클릭하면 문제 사이트로 이동합니다.

 

 

💭 문제 이해

 

역시 탐색문제로 BFS를 이용하여 풀어야 한다.

여섯 방향으로 동시에 진행하므로 너비 우선 탐색이 맞다고 판단하였다.

 

다른 문제와 차이점이라면 3차원 리스트를 이용하여야 한다는 점인데,

arr[깊이][가로][세로] 인 것을 유의하여야 하는 문제이다.

 

 

 

 

구현 언어: Python

 

import sys
from collections import deque

# 3차원 리스트는 arr[깊이][가로][세로]로 구성
# col, rol, height
m, n, h = map(int, sys.stdin.readline().rstrip().split())
warehouse = [[list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)] for _ in range(h)]
queue = deque()
# 상 하 좌 우 앞 뒤
mx = [-1, 1, 0, 0, 0, 0]
my = [0, 0, -1, 1, 0, 0]
mz = [0, 0, 0, 0, -1, 1]

# 모든 토마토가 익어있는 상태 체크
all_ripen = True
for level in warehouse:
    for row in level:
        if 0 in row:
            all_ripen = False

if all_ripen:
    print(0)
    sys.exit()


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

while queue:
    z, x, y = queue.popleft()
    for t in range(6):
        nx = x + mx[t]
        ny = y + my[t]
        nz = z + mz[t]
        if 0 <= nx < n and 0 <= ny < m and 0 <= nz < h:
            if warehouse[nz][nx][ny] == 0:
                warehouse[nz][nx][ny] = warehouse[z][x][y] + 1
                last_val = warehouse[nz][nx][ny]
                queue.append((nz, nx, ny))


# 작업 끝난 후 토마토 상태 체크
all_ripen = True
for level in warehouse:
    for row in level:
        if 0 in row:
            all_ripen = False

if not all_ripen:
    print(-1)
else:
    # 시작일을 포함한 값이므로 -1
    print(last_val - 1)