[Python] BOJ/백준 7569번 토마토

[문제]

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

7569번: 토마토

[풀이]

이 문제는.. 지문에 나와있는 `최소 일수`,  `인접한 여섯 방향의 토마토가 익음` 키워드로 bfs 문제임을 알 수 있다.

최소 일수를 구하는 문제는 bfs를 이용한다.

 

이전에 풀었던 7576 토마토 문제 + 2차원 의 문제이다.

해당 문제가 어렵고 7576번을 아직 풀지 않았다면 .. 7576번부터 먼저 풀면 도움이 될 것 같다.

2022.06.22 - [문제풀이/BOJ] - [Python] BOJ/백준 7576번 토마토

[Python] BOJ/백준 7576번 토마토

 

7576의 설명과 마찬가지로 첫 번째 날에 토마토 박스에 1이 여러 곳에 위치해 있을 경우 동시다발적으로 각 위치를 기준으로 6 방향의 토마토가 익어야하기 때문에 main에서 bfs 함수를 부를 때 상자에 저장된 토마토들의 초기 정보 한바퀴 전체를 돌아 deque에 담은 후 한번에 bfs 함수의 인자로 보내주었다.

 

하루의 단위는 temp_tomato라는 여분의 데크를 만들어 하루동안 익은 토마토를 차례대로 넣은 후

미리 tomato에 넣어둔(=어제 익었던 토마토) 토마토들이 다 pop 되어 큐가 비어있을 경우(: if not tomato) 하루가 지난 것으로 간주했다. 따라서 이 경우 cnt 변수를 1 증가시키고 tomato에 temp_tomato를 옮겨담은 후 temp_tomato를 빈 데크로 다시 초기화해준다.

 

이전에 일차원 토마토 문제를 풀 때는 나름 수월하게 풀었지만 z축도 추가되다 보니 반복문 내에서 조금 헷갈렸다.

뭐.............. 문제를 많이 풀다보면 점점 괜찮아지겠지 (이번에 한번에 문제 맞은 것도 큰 발전이라 생각)

그나저나 계속 풀다보니 bfs 문제 재밌다

 

[코드]

import sys
from collections import deque


def bfs(tomato):
    # 위, 아래, 왼쪽, 오른쪽, 앞, 뒤
    dx = [0, 0, -1, 1, 0, 0]    # 열
    dy = [0, 0, 0, 0, -1, 1]    # 행
    dz = [1, -1, 0, 0, 0, 0]    # 높이

    cnt = 0
    tomato = deque(tomato)
    temp_tomato = deque()
    while tomato:
        z, y, x = tomato.popleft()  # z: 높이, y: 행, x: 열

        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]
            if 0 <= nx < m and 0 <= ny < n and 0 <= nz < h:
                if box[nz][ny][nx] == 0:
                    temp_tomato.append((nz, ny, nx))
                    box[nz][ny][nx] = 1

        if not tomato:
            cnt += 1
            tomato.extend(temp_tomato)
            temp_tomato = deque()

    return is_all_ripe(cnt)


def is_all_ripe(cnt):
    for i in range(h):
        for j in range(n):
            for k in range(m):
                if box[i][j][k] == 0:
                    cnt = 0
    return cnt - 1


m, n, h = map(int, sys.stdin.readline().split())
box = []
for _ in range(h):
    temp_box = []
    for _ in range(n):
        temp_box.append(list(map(int, sys.stdin.readline().split())))
    box.append(temp_box)

tomato = []
for i in range(h):
    for j in range(n):
        for k in range(m):
            if box[i][j][k] == 1:
                tomato.append((i, j, k))
print(bfs(tomato))