🥇 7569 토마토
문제
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.
입력
정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -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)