창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.
정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.
토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다.
7576 토마토 문제의 3차원 버전이다. 기존 문제에서 토마토가 익는 방향(위, 아래)가 추가되었으며 기본적인 논리 흐름은 같다. 큐에 익은 토마토만 먼저 추가하고, 탐색하면서 안 익은 토마토들을 방문하면서 visited 배열의 값을 1씩 증가시켜준다.
마지막으로 visited 배열에서 가장 높은 값을 뽑아내어 -1해주면 된다. 여기서 0인 칸을 발견했을 경우는 토마토가 익지 못했다고 볼 수 있기 때문에 -1을 출력해주고 프로그램을 종료시킬 수 있도록 했다.
import sys
from collections import deque
input = sys.stdin.readline
# 사각형의 크기, 높이
m, n, h = map(int, input().split())
boxes = []
for _ in range(h):
# 1: 익은 토마토, 0: 익지 않은 토마토, -1: 빈 칸
tmp = [list(map(int, input().split())) for _ in range(n)]
boxes.append(tmp)
visited = [[[0 for _ in range(m)] for _ in range(n)] for _ in range(h)]
q = deque()
for i in range(h):
for j in range(n):
for k in range(m):
# 익은 토마토일 경우에만 큐에 삽입
if boxes[i][j][k] == 1:
q.append((i, j, k))
visited[i][j][k] = 1
# 빈 공간인 경우 방문 처리
elif boxes[i][j][k] == -1:
visited[i][j][k] = 1
while q:
depth, x, y = q.popleft()
# 토마토와 인접한 곳 : 위, 아래, 상하좌우
for nd, nx, ny in (depth - 1, x, y), (depth + 1, x, y), (depth, x + 1, y), (depth, x - 1, y), (depth, x, y - 1), (depth, x, y + 1):
if nx < 0 or ny < 0 or nd < 0 or nx >= n or ny >= m or nd >= h:
continue
if not visited[nd][nx][ny]:
visited[nd][nx][ny] += visited[depth][x][y] + 1
q.append((nd, nx, ny))
max_value = -987654321
for i in range(h):
for j in range(n):
for k in range(m):
# 방문을 못한 칸이므로 토마토가 익지 못함
if visited[i][j][k] == 0:
print(-1)
exit(0)
max_value = max(max_value, visited[i][j][k])
print(max_value - 1)