[백준] 토마토(골드5)

문제 링크 

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

 

bfs(그중에서도 멀티소스 bfs) 이용 문제

1. 시작이 맨 첫번째 인덱스에서가 아님

-> 3중 for문을 돌며 익은 토마토를 모두 큐에 삽입

 

2. 큐를 돌며 익은 토마토의 아래 위 왼쪽 오른쪽 앞 뒤를 현재 익은 토마토 값 + 1 을 해서 넣어줌 -> 최소 일수를 구하는 핵심 포인트

이 값이 최소 일수를 의미

 

3. 큐 요소들이 모두 소진되면 3중 for문을 통해 그래프를 돌며 모든 토마토가 익었는지 답이 무엇인지 확인함

- 여기서 max를 통해 일수를 찾는데 왜 최소 일수를 찾으면서 최대 일수를 구하나 라는 의문이 생길 수 있음

<- 모든 토마토가 익는 순간을 구하려면, 가장 늦게 익은 토마토가 익은 날짜를 알아야함

 

구현 코드

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

def bfs(m, n, h, graph):
    q = deque()

    # 익은 토마토 모두 큐에 삽입
    for z in range(h):
        for y in range(n):
            for x in range(m):
                if graph[z][y][x] == 1:
                    q.append((x, y, z))

    dx_dy_dz = [(0, 0, 1), (0, 0, -1), (-1, 0, 0), (1, 0, 0), (0, -1, 0), (0, 1, 0)]

    while q:
        x, y, z = q.popleft()
        for dx, dy, dz in dx_dy_dz:
            nx, ny, nz = x + dx, y + dy, z + dz
            if 0 <= nx < m and 0 <= ny < n and 0 <= nz < h:
                if graph[nz][ny][nx] == 0:
                    graph[nz][ny][nx] = graph[z][y][x] + 1
                    q.append((nx, ny, nz))

    # 모두 탐색이 끝난 후 날짜 계산
    days = 0
    for z in range(h):
        for y in range(n):
            for x in range(m):
                if graph[z][y][x] == 0:
                    return -1
                days = max(days, graph[z][y][x])
    return days - 1

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