[Python] 백준/BOJ 7569번: 토마토 (Gold 5)

💻 Problem

문제 보러 가기

 

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

각 칸은 익은 토마토(1), 익지 않은 토마토(0), 빈칸(-1) 중 하나이다.

보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 

하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다.

철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

 

💡 Approach

7576. 토마토 문제의 3차원 버전이다.

문제 풀이 방식, 코드는 거의 같다. 거기에 높이만 추가하면 된다.

 

1. 익은 토마토가 있는 칸들을 찾아서 큐에 위치를 저장한다.
2. 익은 토마토가 있는 칸에서 탐색을 시작한다.
3. 현재 위치에서 같은 높이의 상하좌우와 위 아래, 6방향을 살펴본다.
4. 다음 칸에 안 익은 토마토가 있으면 토마토를 익게 만든다.
   1. 토마토를 익게 하는데 하루가 소요된다.
   2. 토마토가 익은 날짜를 해당 칸에 기록한다. (이전 칸 + 1)
5. 박스에서 가장 큰 숫자가 기록되어 있는 칸을 찾는다.

 

5번에서 찾은 칸에 기록된 숫자가 모든 토마토가 익는 데에 걸리는 최소 날짜이다.

처음 익은 토마토 칸이 1이므로 걸린 날짜는 하루를 빼야 한다.

 

✏️ Solution

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

def bfs():
    dz = [0, 0, 0, 0, -1, 1]
    dx = [-1, 1, 0, 0, 0, 0]
    dy = [0, 0, -1, 1, 0, 0]

    while queue:
        z, x, y = queue.popleft()

        # 같은 높이의 상하좌우와 위, 아래를 탐색한다
        for i in range(6):
            nz = z + dz[i]
            nx = x + dx[i]
            ny = y + dy[i]

            # 범위를 벗어나면 탐색하지 않는다
            if nz < 0 or nz >= height or nx < 0 or nx >= row_size or ny < 0 or ny >= col_size:
                continue

            # 안익은 토마토가 있는 칸이면 하루를 더해서 기록한다
            # 다음 토마토를 탐색한다
            if boxes[nz][nx][ny] == 0:
                boxes[nz][nx][ny] = boxes[z][x][y] + 1
                queue.append((nz, nx, ny))

col_size, row_size, height = map(int, input().split())
boxes = [[list(map(int, input().split())) for _ in range(row_size)] for _ in range(height)]
queue = deque()
days = 0 # 토마토가 모두 익을 때까지의 최소 날짜

# 익은 토마토가 있는 칸을 모두 찾아 위치를 저장한다
for i in range(height):
    for j in range(row_size):
        for k in range(col_size):
            if boxes[i][j][k] == 1:
                queue.append((i, j, k))

bfs()

for box in boxes:
    for row in box:
        # 토마토가 모두 익지는 못하는 상황이면 -1을 출력한다
        if 0 in row:
            print(-1)
            exit(0)
        days = max(days, max(row))

# 시작이 1이므로 하루는 제외한다
print(days - 1)

시간복잡도: O(row_size * col_size * height)

row_size, col_size, height의 최댓값은 100이다.

100 * 100 * 100 = 1,000,000 = 10 ^ 6

1억(10 ^ 8) 보다 작으므로 시간제한 1초에 문제 되지 않는다.