[백준 7569] 토마토

문제 바로가기

문제 분류

가중치가 없는 그래프에서 다중 시작점에서부터 모든 칸까지의 최단 거리를 구하는 문제
출처 - https://solved.ac/contribute/7569

bfs

알고리즘 - [백준 7576] 토마토와 동일

1. 익은 토마토의 위치를 queue에 삽입
2. queue의 익은 토마토들을 dfs로 순회하며 주변의 안익은 토마토를 익음 처리하고 queue에 삽입. 순회할 때마다 날짜 변수 date를 갱신한다.
3. date를 반환

from collections import deque

m, n, h = map(int, input().split())
board_stacked = list()
for i in range(h):
    board = list()
    for j in range(n):
        board.append(list(map(int, input().split())))
    board_stacked.append(board)


def dfs(r_len, c_len, h_len, board, q):
    date = -1
    while q:
        date += 1
        same_depth = len(q)
        for i in range(same_depth):
            h, r, c = q.popleft()
            adjacencies = [
                (h, r - 1, c),
                (h, r, c + 1),
                (h, r + 1, c),
                (h, r, c - 1),
                (h - 1, r, c),
                (h + 1, r, c),
            ]
            for h_next, r_next, c_next in adjacencies:
                if (
                    0 <= h_next < h_len
                    and 0 <= r_next < r_len
                    and 0 <= c_next < c_len
                    and board[h_next][r_next][c_next] == 0
                ):
                    board[h_next][r_next][c_next] = 1
                    q.append((h_next, r_next, c_next))
    return date


def solution(m, n, h, board):
    unripe_tomato = False
    for height in range(h):
        for row in range(n):
            if 0 in board[height][row]:
                unripe_tomato = True
                break
        if unripe_tomato:
            break
    else:
        # 이미 다 익어있는 경우
        return 0

    q = deque()
    for height in range(h):
        for row in range(n):
            for col in range(m):
                if board[height][row][col] == 1:
                    q.append((height, row, col))

    answer = dfs(n, m, h, board, q)

    for height in range(h):
        for row in range(n):
            if 0 in board[height][row]:
                # 토마토가 모두 익지는 못하는 상황
                return -1
    return answer


print(solution(m, n, h, board_stacked))