6115 : 토마토
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
3차원 격자 상자(가로 M, 세로 N, 높이 H)에 들어있는 토마토들이 하루에 한 번 상하좌우 및 위아래 총 6방향으로 익지 않은 인접 토마토를 익힙니다.
격자 내의 익은 토마토(1), 익지 않은 토마토(0), 토마토가 없는 빈칸(-1)이 주어질 때 모든 토마토가 익는 데 걸리는 최소 일수를 구하시오.
격자 내의 익은 토마토(1), 익지 않은 토마토(0), 토마토가 없는 빈칸(-1)이 주어질 때 모든 토마토가 익는 데 걸리는 최소 일수를 구하시오.
입력 설명
첫째 줄에 가로 M, 세로 N, 높이 H (1 ≤ M, N, H ≤ 100)가 주어집니다.
둘째 줄부터 H×N개의 줄에 걸쳐 격자의 정보(1, 0, -1)가 공백 구분되어 주어집니다.
둘째 줄부터 H×N개의 줄에 걸쳐 격자의 정보(1, 0, -1)가 공백 구분되어 주어집니다.
출력 설명
토마토가 모두 익을 때까지의 최소 일수를 출력합니다. 이미 다 익어 있으면 0, 일부가 다 익을 수 없는 고립된 구조라면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 3 1
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
-1도움
2차원 격자의 상하좌우를 넘어 3차원 축의 6방향 변위
dz = [-1, 1, 0, 0, 0, 0] 등을 추가로 적용하고, 다중 시작지점 BFS를 돌려 최대 일수를 갱신하면 해결할 수 있습니다.