백준 7569: 토마토 Python (BFS)

 

 

이번 문제는 3차원으로 생각해야 해서 처음 접근하기가 어려웠는데 기존 4방향 탐색에서 6방향 탐색으로 바꿔주기만 하면 됐다.

처음에는 기존 하던 방식대로 for문을 돌려 토마토가 1일 때마다 bfs를 실행했는데, 그렇게 하면 런타임에러가 난다.

따라서 처음 상태가 1(익은 상태)이었던 토마토들을 미리 queue에 넣고, 그 queue에 대해서 한 번만 bfs를 해야 했다.

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


def bfs():
    while q:
        sh, si, sj = q.popleft()
        for dh, di, dj in [(-1, 0, 0), (1, 0, 0), (0, -1, 0), (0, 1, 0), (0, 0, -1), (0, 0, 1)]:
            nh, ni, nj = sh+dh, si+di, sj+dj
            if 0 <= nh < H and 0 <= ni < N and 0 <= nj < M:
                if arr[nh][ni][nj] == 0 and not visited[nh][ni][nj]:
                    arr[nh][ni][nj] = arr[sh][si][sj] + 1
                    visited[nh][ni][nj] = 1
                    q.append((nh, ni, nj))


M, N, H = map(int, input().split())     # M: 세로, N: 가로, H: 높이
arr = list([[0] * M for _ in range(N)] for _ in range(H))

for h in range(H):
    for i in range(N):
        arr[h][i] = list(map(int, input().split()))

visited = list([[0] * M for _ in range(N)] for _ in range(H))   # 방문체크

# 상자에 있는 토마토 중 익은 토마토들을 queue에 넣는다
q = deque()
for h in range(H):
    for i in range(N):
        for j in range(M):
            if arr[h][i][j] == 1:
                q.append((h, i, j))

bfs()

# 끝까지 익지 않은 토마토가 있는지 체크
flag = False
answer = 0
for h in range(H):
    for i in range(N):
        for j in range(M):
            if arr[h][i][j] == 0:
                flag = True
                break
            answer = max(answer, arr[h][i][j])

if flag:
    answer = -1
elif answer == -1:
    answer = 0
else:
    answer -= 1

print(answer)