[알고리즘/baekjoon] 7569_토마토2(python)

문제

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

7569번: 토마토

# 기존의 2차원 배열이 아닌 3차원으로 생각해야 하는 문제이다. 최소 일수를 구하는 문제이므로 bfs(=deque)를 사용하자

# 높이가 배열에서 표현되면 제일 앞에 표현되는 것만 주의하자

 

정답

import sys
from collections import deque
input = sys.stdin.readline
m, n, h = map(int, input().split())
box = [[list(map(int, input().split())) for _ in range(n)] for _ in range(h)] # 3차원 리스트로 표현
 
# 익은 토마토를 큐에 넣음
queue = deque()
for i in range(h):
    for j in range(n):
        for k in range(m):
            if box[i][j][k] == 1: # 익은 토마토라면 q에 저장
                queue.append((i, j, k, 0))
 
# 방향지시자(x,y,z방향 생각 -> 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향)
dz = [-1, 1, 0, 0, 0, 0]
dx = [0, 0, -1, 1, 0, 0]
dy = [0, 0, 0, 0, -1, 1]
 
while queue:
    z, x, y, days = queue.popleft()
 
    # 인접위치 토마토 확인
    for i in range(6):
        nz = z + dz[i]
        nx = x + dx[i]
        ny = y + dy[i]
        ndays = days + 1
 
        # 박스 영역 안인지 확인
        if 0 <= nx < n and 0 <= ny < m and 0 <= nz < h:
            # 안익은 토마토일 경우 익힘 처리 후 큐에 삽입
            if box[nz][nx][ny] == 0:
                box[nz][nx][ny] = 1
                queue.append((nz, nx, ny, ndays))
 
# 익지 않은 토마토가 있을 경우 결과값 -1로 변경
for i in range(h):
    for j in range(n):
        if box[i][j].count(0) > 0:
            days = -1
            break
 
print(days)