[BOJ] 7569번 토마토 - Python

문제

7569번: 토마토

 

 

풀이

• 처음에 익을 수 없는 경우의 수를 먼저 체크해주는 것이 좋겠다고 생각했다. 
• 이번에는 큐에 넣어주어야 하는 경우가 두 가지 더 추가되었었다. (위층, 아래층)
• 예외적인 상황은 먼저 이른 리턴해주어서 가지치는 것도 특정 케이스에서 복잡도를 줄이는 방법 중 하나 인 것 같다.

from collections import deque


# TODO: 토마토가 익는 최소 일 수 구하기 🪀
def solution(h, n, m, board):
    if check_already_ripen(h, n, m, board):  # 초기 검증
        return 0

    visited = [[[False] * m for _ in range(n)] for _ in range(h)]
    days = bfs(visited, board, n, m, h)

    if check_impossible_to_ripen(h, n, m, board):  # 검증
        return -1
    return days


def bfs(visited, board, n, m, h):
    day = 0
    dv = [0, 0, 0, 0, 1, -1]
    dr = [0, 0, 1, -1, 0, 0]
    dc = [1, -1, 0, 0, 0, 0]
    queue = deque()
    for c in range(m):
        for r in range(n):
            for v in range(h):
                if not visited[v][r][c] and board[v][r][c] == 1:  # 현재 익어 있어야만 영향 끼칠 수 있음
                    queue.append((v, r, c, 0))
                    visited[v][r][c] = True

    while queue:
        v, r, c, day = queue.popleft()
        for i in range(6):
            nv = v + dv[i]
            nr = r + dr[i]
            nc = c + dc[i]
            if nr < 0 or nr >= n or nc < 0 or nc >= m or nv >= h or nv < 0:
                continue
            if visited[nv][nr][nc] or board[nv][nr][nc] != 0:
                continue
            queue.append((nv, nr, nc, day + 1))
            visited[nv][nr][nc] = True
            board[nv][nr][nc] = 1
    return day


def check_already_ripen(h, n, m, board):
    num_tomato = 0
    for c in range(m):
        for r in range(n):
            for v in range(h):
                if board[v][r][c] == 1 or board[v][r][c] == -1:
                    num_tomato += 1
    if num_tomato == n * m * h:
        return True
    return False


def check_impossible_to_ripen(h, n, m, board):
    for c in range(m):
        for r in range(n):
            for v in range(h):
                if board[v][r][c] == 0:
                    return True
    return False


M, N, H = map(int, input().split())
board = [[list(map(int, input().split())) for _ in range(N)] for _ in range(H)]
print(solution(H, N, M, board))