[백준] 7569번 토마토 파이썬 풀이

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

7569번: 토마토

---

1. 접근 방식

• 3차원 리스트를 사용하자.

기존 2차원 리스트에서 상하좌우를 이동할 때 direction = [ [1, 0], [0, 1], [0, -1], [0, 1] ]이라는 방향 리스트를 사용했던 것을 떠올려보자. 이 문제에서는 단순히 높이라는 하나의 차원이 더해졌을 뿐이므로, 기본 접근 방식은 동일하다. 토마토를 n x m 크기의 상자에 담는데, 이 상자가 h개일 뿐이다.

따라서 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 방향 리스트는 direction = [[0, -1, 0], [0, 1, 0], [0, 0, -1], [0, 0, 1], [1, 0, 0], [-1, 0, 0]]이다.

 

 

• 3차원이라는 것만 제외하면 기본 너비 우선 탐색(BFS)과 동일한 코드이다.

 

 

• 처음 시작에 익은 토마토의 위치를 파악하자.

하나의 특정 위치에서 탐색을 시작하지 않고, 모든 익은 토마토에서부터 탐색을 시작한다. 따라서 처음에 너비 우선 탐색을 시작하기 전에 익은 토마토의 위치를 파악해야 하므로, find_ripen_tomatoes() 메서드를 작성한다.

 

 

 

2. 정답 코드

from collections import deque
import sys

input = sys.stdin.readline

def find_ripen_tomatoes():
    ripen = []
    for x in range(h):
        for y in range(n):
            for z in range(m):
                if boxes[x][y][z] == 1:
                    ripen.append([x, y, z])
    return ripen

def bfs():
    qu = deque(find_ripen_tomatoes())

    while qu:
        a, b, c = qu.popleft()

        for d in direction:
            dx = a + d[0]
            dy = b + d[1]
            dz = c + d[2]

            if dx < 0 or dx >= h or dy < 0 or dy >= n or dz < 0 or dz >= m:
                continue

            if boxes[dx][dy][dz] == 0:
                boxes[dx][dy][dz] = boxes[a][b][c] + 1
                qu.append([dx, dy, dz])

def findToTalDays():
    days = 0
    for x in range(h):
        for y in range(n):
            for z in range(m):
                if boxes[x][y][z] == 0:
                    return -1
                days = max(days, boxes[x][y][z])

    return days - 1

# main
m, n, h = map(int, input().split())
boxes = [[list(map(int, input().split())) for _ in range(n)] for _ in range(h)]
direction = [[0, -1, 0], [0, 1, 0], [0, 0, -1], [0, 0, 1], [1, 0, 0], [-1, 0, 0]]

bfs()
print(findToTalDays())