정말 옛날에 한창 BFS 공부하던 시절. 풀고 정말 뿌듯했던 문제를 풀이해볼까 한다.

BOJ 7569 - 토마토 링크
(2022.09.27 기준 G5)
(치팅 NOPE!)

문제

가로 칸의 수는 M, 세로 칸의 수는 N인 토마토가 들어있는 상자가 있고 쌓아올려지는 상자의 수는 H이다.
익은 토마토랑 인접한 익지 않은 토마토는 하루 후 익는다고 했을 때, 모든 토마토가 익는 최소 일수

알고리즘

인접한 곳으로 서서히 퍼져나가므로 BFS

풀이

BFS 문제의 본격적인 시작이자 기본 문제이다.
BFS 알고리즘은 공부하고 오자.

일단 이 문제는 익은 토마토들로부터 BFS를 시작해야 한다. 즉, 시작점이 여러 개란 뜻이다.
그리고 익은 토마토는 1, 익지 않은 토마토는 0, 토마토가 들어있지 않은 칸은 -1이고 BFS를 할 때에 익지 않은 토마토를 찾아가야 한다. 그러므로 토마토가 들어있지 않은 칸은 전부 1로 바꿔주고, BFS에서 익지 않은 토마로를 찾아갈 때마다 1로 바꿔주면 된다.

일단 처음에 덱을 하나 만들어두고, 하나하나 탐색하면서 익은 토마토를 발견하면 덱에 위치를 저장하면 된다. 그리고 토마토가 들어 있지 않은 칸은 위에서 말했듯이 1로 바꾸자.
그리고 남은 익지 않은 토마토 개수도 세어가면 좋다.
처음엔 M * N * H으로 저장해두고 익은 토마토나 토마토가 들어있지 않은 칸을 발견할 때마다 1씩 감소시키면 된다. 그리고 0이 되면 알맞는 답 출력 후 즉시 프로그램 종료하면 시간 최적화가 될 것이다.

이제 익은 토마토들로부터 BFS를 시작하면 되는데, 정말 간단하다. 상하좌우앞뒤 육방향으로 탐색하고, 모든 토마토가 익으면 일수 출력하고 익지 않았으면 -1을 출력하면 된다.

코드

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

def solve():
    M, N, H = map(int, input().split())
    tomato_box = [[list(map(int, input().split())) for _ in range(N)] for __ in range(H)]
    
    # 익은 토마토들부터 BFS를 시작해야 한다.
    # 그래서 익은 토마토들을 찾아서 덱에 저장하자.
    # BFS를 돌릴 때, 익지 않은 토마토 0을 찾아갈 것이므로
    # 토마토가 들어있지 않은 칸은 1로 바꿔두자.
    queue = deque() # 익은 토마토들의 위치 저장
    rest = M * N * H # 남은 토마토 개수
    for h in range(H): # 탐색 시작
        for n in range(N):
            for m in range(M):
                if tomato_box[h][n][m] == 1: # 익은 토마토일 경우
                    queue.append((h, n, m, 0)) # 위치와 일수를 저장. 0일부터 시작해야 한다.
                    rest -= 1 # 남은 토마토 개수 감소
                elif tomato_box[h][n][m] == -1: # 토마토가 들어있지 않은 칸일 경우
                    tomato_box[h][n][m] = 1 # 1로 저장
                    rest -= 1 # 남은 토마토 개수 감소
    
    # 모든 토마토가 익어있으면 0 출력 후 프로그램 종료
    if not rest:
        print(0)
        return
    
    # BFS 시작
    while queue:
        h, n, m, days = queue.popleft()
        # 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향으로 탐색
        # 각 방향은 범위 안이어야 하고, 익지 않은 토마토가 들어 있는 칸이어야 한다.
        for hh, nn, mm in [(h - 1, n, m), (h + 1, n, m), (h, n - 1, m), (h, n + 1, m), (h, n, m - 1), (h, n, m + 1)]:
            if 0 <= hh < H and 0 <= nn < N and 0 <= mm < M and not tomato_box[hh][nn][mm]:
                rest -= 1
                if not rest: # 다음 방향의 토마토가 익어서 남아있는 토마토가 없게 되면
                    print(days + 1) # 다음 방향의 토마토가 익는 날을 출력 후
                    return # 프로그램 종료
                queue.append((hh, nn, mm, days + 1))
                tomato_box[hh][nn][mm] = 1
    else: # 덱 탐색이 끝났는데도 프로그램 종료가 되지 않았다면
        print(-1) # 토마토가 모두 익지 못하는 상황이므로 -1 출력

solve()

여담

제일 좋은 풀이를 적기 위해 열심히 최적화를 한 흔적.
이 정도만 해도 나쁘지 않은 풀이인 듯 하다.

그리고 BOJ 7576 - 토마토 문제는 이 문제와 같다. 다른 점은 이 문제는 3차원, 저 문제는 2차원. 더 쉽다는 뜻이다.
그러므로 이 문제 풀었으면 저 문제는 공짜니깐 얼른 가서 AC를 받아내자.