[Python] 7576 - 토마토

[Gold V] 토마토 - 7569 

[문제 링크](https://www.acmicpc.net/problem/7569) 

🗝️알고리즘 분류

• 그래프 탐색
• 너비 우선 탐색 (BFS)

---

💻문제 정의

NxM 크기의 격자모양의 상자에 익은 토마토와 익지 않은 토마토가 들어있다. 해당 상자는 위로 쌓여있을 수도 있다. 익은 토마토의 상, 하, 좌, 우, 앞, 뒤 6방향의 토마토는 하루가 지나면 익게된다. 모든 토마토가 익을 때 까지 며칠이 걸리는지 구하는 문제이다.

 

💡접근 및 설계

익은 토마토는 1, 익지 않은 토마토는 0, 빈 공간은 -1로 주어진다. 익은 토마토를 기준으로 상, 하, 좌, 우, 앞, 뒤 6방향에 존재하는 토마토는 하루가 지나면 익게된다. 이 토마토들의 상, 하, 좌, 우, 앞, 뒤 6방향에 존재하는 토마토는 이틀이 지나면 익게된다. 이러한 방식으로 BFS를 이용하여 상자 내 모든 토마토를 탐색하며 익는데 걸리는 시간을 계산한다.

 

✏️알고리즘 풀이

visited = [[[False for _ in range(N)] for _ in range(M)] for _ in range(H)]
Q = deque()

# 토마토 위치 찾기
for h in range(H):
    for y in range(M):
        for x in range(N):
            if (graph[h][y][x] == 1):
                Q.append([h, y, x])
                visited[h][y][x] = 1

while Q:
    ch, cy, cx = Q.popleft()

    for i in range(6):
        nh = ch + dh[i]
        ny = cy + dy[i]
        nx = cx + dx[i]

        if (0 <= nh < H) and (0 <= ny < M) and (0 <= nx < N) and (graph[nh][ny][nx] == 0) and not visited[nh][ny][nx]:
            Q.append([nh, ny, nx])
            visited[nh][ny][nx] = visited[ch][cy][cx] + 1

그래프 전체를 돌며 익은 토마토의 위치를 deque에 저장한다. deque에 저장된 정보를 바탕으로 bfs를 진행한다.

visited 리스트에 언제 익었는지를 표시한다.

 

for h in range(H):
    for y in range(M):
        for x in range(N):
            if not visited[h][y][x] and graph[h][y][x] == 0:
                print(-1)
                exit(0)

탐색을 마친 후, 그래프 전체를 돌며 익지 않은 토마토가 존재하는지 확인한다. 만약 존재한다면 이는 모든 토마토가 익을 수 없는 상자이므로 -1을 출력하고 실행을 끝낸다.

 

max_value = 0
for h in range(H):
    for y in range(M):
        for x in range(N):
            max_value = max(max_value, visited[h][y][x])

print(max_value - 1 if max_value != 1 else 0)

visited를 돌며 가장 큰 값 즉, 익는데 가장 오래 걸린 토마토의 일수를 구한다. 만약 익는데 가장 오래 걸린 토마토의 일수가 1일 경우 이는 처음부터 모든 토마토가 익은 상태이기에 0을 출력한다.

 

🗒️제출 코드

# 7569 토마토

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

N, M, H = map(int, input().split())

# 상, 하, 좌, 우, 앞, 뒤
dx = [0, 0, -1, 1, 0, 0]
dy = [1, -1, 0, 0, 0, 0]
dh = [0, 0, 0, 0, 1, -1]

graph = []
for _ in range(H):
    graph_2 = []
    for _ in range(M):
        graph_2.append(list(map(int, input().split())))
    graph.append(graph_2)

visited = [[[False for _ in range(N)] for _ in range(M)] for _ in range(H)]
Q = deque()

# 토마토 위치 찾기
for h in range(H):
    for y in range(M):
        for x in range(N):
            if (graph[h][y][x] == 1):
                Q.append([h, y, x])
                visited[h][y][x] = 1

while Q:
    ch, cy, cx = Q.popleft()

    for i in range(6):
        nh = ch + dh[i]
        ny = cy + dy[i]
        nx = cx + dx[i]

        if (0 <= nh < H) and (0 <= ny < M) and (0 <= nx < N) and (graph[nh][ny][nx] == 0) and not visited[nh][ny][nx]:
            Q.append([nh, ny, nx])
            visited[nh][ny][nx] = visited[ch][cy][cx] + 1

for h in range(H):
    for y in range(M):
        for x in range(N):
            if not visited[h][y][x] and graph[h][y][x] == 0:
                print(-1)
                exit(0)

max_value = 0
for h in range(H):
    for y in range(M):
        for x in range(N):
            max_value = max(max_value, visited[h][y][x])

print(max_value - 1 if max_value != 1 else 0)

---