[Python] 백준 7569 - 토마토 문제 풀이

Overview

BOJ 7569번 토마토 Python 문제 풀이
분류: Graph Traversal (그래프 탐색), bfs

[Python] 백준 7576 - 토마토 문제 풀이 를 응용한 문제

---

문제 페이지

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

---

풀이 코드

from sys import stdin
from collections import deque


def main():
    def input():
        return stdin.readline().rstrip()

    M, N, H = map(int, input().split())
    box = []
    unriped = 0
    dq = deque()

	# 덜익은 토마토 탐색
    for i in range(H):
        layer = []
        for j in range(N):
            layer.append(list(map(int, input().split())))
            for k in range(M):
                if layer[j][k] == 0:
                    unriped += 1
                elif layer[j][k] == 1:
                    dq.append((i, j, k, 1))
        box.append(layer)

	# 탐색 방향 (상하동서남북)
    dz = [1, 0, 0, 0, 0, -1]
    dy = [0, 1, -1, 0, 0, 0]
    dx = [0, 0, 0, 1, -1, 0]
    
    # bfs 탐색
    res = 0
    while unriped > 0 and dq:
        cz, cy, cx, res = dq.popleft()
        for i in range(6):
            nz, ny, nx = cz + dz[i], cy + dy[i], cx + dx[i]
            if 0 <= nz < H and 0 <= ny < N and 0 <= nx < M \
                    and box[nz][ny][nx] == 0:
                unriped -= 1
                dq.append((nz, ny, nx, res + 1))
                box[nz][ny][nx] = 1

    if not dq:
        res = -1

    print(res)


if __name__ == "__main__":
    main()

[Python] 백준 7576 - 토마토 문제 풀이 와 아이디어는 같다.
bfs를 응용한 탐색방법으로 익은 토마토와 덜 익은 토마토를 조사한다.
만약 익은 토마토의 상하좌우 위치에 덜익은 토마토가 있는 경우, deque에 해당 위치와 날짜를 저장한다. 그리고 deque에서 pop 될 때는 해당 토마토는 익은 토마토로 처리하고 이전 내용을 반복한다.
위 bfs 응용 탐색을 상자의 토마토가 모두 익거나 덜익은 토마토 만큼 반복하고, 결과를 출력한다.