|
import sys
input = sys.stdin.readline
from collections import deque
n, m, h = map(int, input().split())
B = []
que = deque()
check = [[[False for i in range(n)] for j in range(m)] for k in range(h)]
for k in range(h) :
B.append([])
for j in range(m) :
B[k].append(list(map(int, input().split())))
for i in range(n) :
t = B[k][j][i]
if t == 1 :
que.append([i, j, k])
dx = [1, -1, 0, 0, 0, 0]
dy = [0, 0, 1, -1, 0, 0]
dz = [0, 0, 0, 0, 1, -1]
while que :
a, b, c = que.popleft()
for i in range(6) :
x = a + dx[i]
y = b + dy[i]
z = c + dz[i]
if 0 <= x < n and 0 <= y < m and 0 <= z < h and B[z][y][x] == 0 and check[z][y][x] == False :
check[z][y][x] = True
B[z][y][x] = B[c][b][a] + 1
que.append([x, y, z])
f = True
date = 0
for k in range(h) :
for j in range(m) :
for i in range(n) :
if B[k][j][i] == 0 :
f = False
date = max(date, B[k][j][i] - 1)
if f :
print(date)
else :
print(-1)
|
dx와 dy를 써서 인접한 블록으로 확산되는 BFS에서 dz를 추가하여 3차원으로 확장한 코드이다.
토마토의 정보가 담긴 3차원 행렬를 인풋대로 작성하고, 익은 토마토는 큐에 넣는다.
인접한 블록이 안익은 토마토라면 익은 토마토의 값 + 1으로 값을 바꾸어 익은 날짜를 구분하고,
check라는 3차원 행렬을 만들어 큐에 담기는 순간 기록하여 큐에 중복으로 담기는 것을 방지한다.
토마토의 값이 익은 날짜 + 1이므로 (처음부터 익어있던 토마토가 1) 안익은 토마토가 없다면 max값을 출력한다.
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
| 파이썬 백준 2294 동전 2 (0) | 2021.11.20 |
|---|---|
| 파이썬 백준 3055 탈출 (0) | 2021.11.20 |
| 파이썬 백준 2665 미로 만들기 (0) | 2021.11.20 |
| 파이썬 백준 1916 최소비용 구하기 (0) | 2021.11.20 |
| 파이썬 백준 18352 특정 거리의 도시 찾기 (0) | 2021.11.20 |