[백준 7569] 토마토 (3차원) ❗

코뉴·2022년 1월 21일

백준🍳

목록 보기

71/149

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

🥚문제

🥚입력/출력

🍳코드

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

m, n, h = map(int, input().split())
box = [[list(map(int, input().split())) for _ in range(n)] for __ in range(h)]


def bfs(q):
    moves = [(-1, 0, 0), (1, 0, 0),
             (0, -1, 0), (0, 1, 0),
             (0, 0, -1), (0, 0, 1)]

    while q:
        level, row, col = q.popleft()

        for move in moves:
            lv = level + move[0]
            r = row + move[1]
            c = col + move[2]
            if 0 <= lv < h and 0 <= r < n and 0 <= c < m:
                if box[lv][r][c] == 0:
                    box[lv][r][c] = box[level][row][col] + 1
                    q.append((lv, r, c))


# deque에 1이 있는 모든 위치를 넣고 시작
q = deque([])
answer = 0
for level in range(h):
    for row in range(n):
        for col in range(m):
            if box[level][row][col] == 1:
                q.append((level, row, col))

# bfs 실행
bfs(q)

# answer는 box에서의 최대값 - 1
answer = 0
for inner in box:
    for row in inner:
        for x in row:
            answer = max(answer, x)
answer -= 1

# 토마토가 모두 익지는 못할 때 = 여전히 0이 존재할 때
for inner in box:
    for row in inner:
        if 0 in row:
            answer = -1
            break

print(answer)

🧂아이디어

상자의 수, 가로칸, 세로칸 -> 3차원 리스트로 나타내기
- box[level][row][col]
1(익은 토마토)가 있는 모든 위치를 deque에 넣고, BFS로 탐색한다 ⭐⭐⭐
토마토가 익는 데 며칠이 걸리는지를 계산하는 방법 🍅
- box[level][row][col]의 값은 토마토가 익는 데 걸리는 일 수 + 1 이라고 생각하자!
- 이미 익은 토마토(box[level][row][col] >= 1)의 위치가 box[level][row][col]이라면
- box[level][row][col]에서 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 방향에 있는 익힐 수 있는 토마토(e.g., box[lv][r][c] == 0)를 발견하면, 그 값을 box[level][row][col] + 1로 갱신 (e.g., box[lv][r][c] = box[level][row][col] + 1)
토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산하는 방법 🍅
- bfs를 하며 익힐 수 있는 토마토를 모두 익힌 뒤,
- 전체 배열에서의 최대 값을 구하고, 여기에서 -1을 해 준 것을 출력!