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

코뉴·2022년 1월 21일
0

백준🍳

목록 보기
71/149
post-custom-banner

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을 해 준 것을 출력!

🙏 반성

어디에서 틀린지 몰라서 1시간을 끙끙댔는데
마지막에 전체 배열에서 최대 값을 구하는 과정에서

max(map(max, map(max, box)))

코드를 사용했다...! 넘나 생각 없이 코드를 짠 결과 없는 반례 찾아내기 지옥이라는 벌을 받았다... 🤦‍♂️
아주 기본적인 거지만, 주의하자는 의미로 이 문제에 대해서는 별개의 게시물로 다시 정리해서 올리자!

profile
코뉴의 도딩기록
post-custom-banner

0개의 댓글