[Python] 토마토(2) - 백준 (BFS)

해당 글은 백준 7569번 문제 '토마토'을 다룬다.

문제

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

7569번: 토마토

 

설명

이전에 풀었던 토마토 백준 문제에서 높이가 추가된 확장문제이다.

이전에 풀었던 BFS 처럼 dh만 추가하여 6가지 방향을 만들면 바로 해결할 수 있다.

 

코드

from collections import deque

c, r, h = map(int, input().split())
boxes = []
for _ in range(h):
    box = []
    for _ in range(r):
        box.append(list(map(int, input().split())))
    boxes.append(box)

dh = [-1, 1, 0, 0, 0, 0]
dx = [0, 0, -1, 1, 0, 0]
dy = [0, 0, 0, 0, 1, -1]
q = deque()

def bfs():
    while q:
        z, x, y = q.popleft()
        for i in range(6):
            nz = z + dh[i]
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= 0 and nx < r and ny >= 0 and ny < c and nz >= 0 and nz < h:
                if boxes[nz][nx][ny] == 0:
                    boxes[nz][nx][ny] = boxes[z][x][y] + 1
                    q.append((nz, nx, ny))


for i in range(h):
    for j in range(r):
        for k in range(c):
            if boxes[i][j][k] == 1:
                q.append((i, j, k))

bfs()

zero_count = 0
max_count = 0
for i in range(h):
    for j in range(r):
        for k in range(c):
            if boxes[i][j][k] == 0:
                zero_count += 1
            max_count = max(max_count, boxes[i][j][k])

if zero_count == 0:
    print(max_count-1)
else:
    print(-1)