[백준] 7569 토마토

문제

• 토마토를 격자모양 상자 칸에 하나씩 넣은 다음 상자들을 수직으로 쌓아 올려 보관한다.
• 보관 후 하루가 지나면 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.
• 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향을 의미한다.
• 며칠이 지나면 토마토가 다 익게 되는지 구하기

 

• 2 <= 가로, 세로 <= 100
  1 <= 높이 <= 100
• 익은 토마토 1, 익지 않은 토마토 0, 토마토 없음 -1
• 토마토가 모두 익지 못하는 상황이면 -1 출력

 

풀이

•  전형적인 그래프 탐색에서 높이 H가 추가된 문제
  상하좌우에서 위, 아래를 추가하면 된다.

 

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

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

dx = (-1, 1, 0, 0, 0, 0)
dy = (0, 0, -1, 1, 0, 0)
dh = (0, 0, 0, 0, -1 ,1)
q = deque()

tomato = []
# 최초의 익은 토마토 추가
for h in range(H) :
    tmp = []
    for i in range(N) :
        tmp.append(list(map(int, input().split())))
        for j in range(M) :
            if tmp[i][j] == 1:
                q.append((h, i, j))
    tomato.append(tmp)

# 토마토 영향
while q :
    h, x, y = q.popleft()

    for i in range(6) :
        nh, nx, ny = h+dh[i], x+dx[i], y+dy[i]
        if 0 <= nh < H and 0 <= nx < N and 0 <= ny < M and tomato[nh][nx][ny] == 0 :
            q.append((nh, nx, ny))
            tomato[nh][nx][ny] = tomato[h][x][y] + 1

# 날짜 세기
day = 0
for h in range(H) :
    for i in range(N) :
        for j in range(M) :
            if tomato[h][i][j] == 0 :
                print(-1)
                exit()
        day = max(day, max(tomato[h][i]))
print(day-1)

 

References

• 백준 그래프 탐색