[백준] 7569번 토마토 (PYTHON)

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

 

문제

 

 

 

# 문제 정리

 

 

철수의 토마토 농장은 3차원 창고 구조로, 여러 층의 상자가 격자 형태로 쌓여 있다.

 

각 칸에는 다음과 같은 상태를 가진 토마토가 있다.

 

1: 익은 토마토

0: 익지 않은 토마토

-1: 토마토가 없는 칸

 

 

익은 토마토는 하루가 지나면 인접한 여섯 방향(위, 아래, 왼쪽, 오른쪽, 앞, 뒤)에 있는 익지 않은 토마토를 익게 만든다.

 

모든 토마토가 익기까지 걸리는 최소 일수를 구하는 것이 목적 !

 

다음 조건을 만족해야 한다.

 

1. 만약 익지 않은 토마토가 모두 익을 수 없는 경우 -1을 출력.
2. 처음부터 모든 토마토가 익어있으면 0을 출력.

 

이에 대한 접근 방식은 3차원 배열로 구성된 그래프 이론 알고리즘으로 접근할 것이다.

 

특히 이번 구성을 queue를 사용해서 탐색할 예정이다.

 

FIFO의 특성을 가진 queue가 일 수 별로 데이터를 인식해서 마지막 우리가 구하고자 하는

 

최소 일 수를 보다 더 빠르게 알 수 있게된다.

 

그렇게 그래프를 통해서 BFS로 탐색을 한다.

 

그러고 내가 구하고자 했던 익은 토마토 (1)을 queue에 넣을 것.

 

0일에 익은 토마토 또한 queue에 넣어야한다.

 

BFS 통해 0이었던 토마토는 1로 변환 시키는 과정을 거치며 queue에 데이터를 넣고  탐색을 진행한다.

 

모든 탐색이 완료가 되면 익지 않은 토마토가 있을 경우에 -1 을 출력하도록 한다.

 

 

 

import sys
from collections import deque

input = sys.stdin.readline


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


dx = [1, -1, 0, 0, 0, 0]
dy = [0, 0, 1, -1, 0, 0]
dz = [0, 0, 0, 0, 1, -1]

queue = deque()


for i in range(h):
    for j in range(n):
        for k in range(m):
            if graph[i][j][k] == 1:
                queue.append((i, j, k))


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


max_days = 0
for i in range(h):
    for j in range(n):
        for k in range(m):
            if graph[i][j][k] == 0: 
                print(-1)
                exit()
            max_days = max(max_days, graph[i][j][k])
            

# 시작일이 1이므로 1을 빼고 출력
print(max_days - 1)

 

 

# 느낀점

 

그래프 이론에 대해서는 C언어로 구현을 많이 해보았지만 파이썬으로 하는 것은 익숙하지 않았다.

 

하지만 이론과 알고리즘에 대한 이해도가 있었기 때문에 꽤 괜찮게 풀어보았다.