[백준 알고리즘] 7569번: 토마토 (Python / 파이썬)

---

문제 접근

[백준 알고리즘] 7576번: 토마토 (Python / 파이썬)

이전에 풀었던 7576번 토마토 문제의 3차원 버전이다.

이때 풀었던 방법과 다르게, 큐에 새로운 익은 토마토를 넣을 때 그 값에 이전 토마토 값 + 1 을 할당하여 날짜 계산을 더 쉽게 처리했다.

주의할 점으로는 시작점이 되는 토마토들이 1의 값을 가지고 있으므로, 위처럼 날짜 계산을 한다면 이 시작 값들은 0이 되거나 마지막에 최댓값을 구하고 1을 빼줘야 한다. 1의 의미는 하루가 지났음의 의미인데 시작할때부터 1이기 때문이다.

3차원에서의 상하좌우 앞뒤 탐색은, 더 쉬운 방법이 있는지 모르겠지만 2차원에서 했던 방법을 응용해서

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

이렇게 세개의 리스트를 만들어 놓고 dx, dy 4번 / dz 2번 나누어서 탐색했다.

 

정답 코드

#7569번: 토마토

import sys
from collections import deque

def bfs():
    queue = deque()
    for riped_tomato in riped_tomatoes:
        queue.append(riped_tomato)

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

    while queue:
        z, x, y = queue.popleft()
        #앞뒤좌우 탐색
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and matrix[z][nx][ny] == 0:
                matrix[z][nx][ny] = matrix[z][x][y] + 1
                queue.append((z, nx, ny))
        #상하 탐색
        for j in range(2):
            nz = z + dz[j]
            if 0 <= nz < h and matrix[nz][x][y] == 0:
                matrix[nz][x][y] = matrix[z][x][y] + 1
                queue.append((nz, x, y))


# 입력부
m, n, h = map(int, sys.stdin.readline().split())
matrix = [[list(map(int, sys.stdin.readline().split())) for _ in range(n)] for _ in range(h)]

# 익어있는 토마토 넣어두기 (시작점)
riped_tomatoes = []
for z in range(h):
    for x in range(n):
        for y in range(m):
            if matrix[z][x][y] == 1:
                riped_tomatoes.append((z, x, y))

bfs()

max = 0
for z in range(h):
    for x in range(n):
        for y in range(m):
            if matrix[z][x][y] == 0:
                print(-1)
                exit()
            if matrix[z][x][y] > max:
                max = matrix[z][x][y]
print(max-1)

---

7569번: 토마토