from collections import deque
dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, -1, 1]
m, n, h = map(int, input().split())
g = []
for i in range(h):
tmp_g = [list(map(int, input().split())) for _ in range(n)]
g.append(tmp_g)
check = [[[-1] * m for _ in range(n)] for _ in range(h)]
def bfs(i, j, k):
q = deque()
check[i][j][k] = 0
q.append((i, j, k))
while q:
a, b, c = q.popleft()
for d in range(6):
na, nb, nc = a + dx[d], b + dy[d], c + dz[d]
if 0 <= na < h and 0 <= nb < n and 0 <= nc < m:
if check[na][nb][nc] == -1 and g[na][nb][nc] == 0:
q.append((na, nb, nc))
check[na][nb][nc] = check[a][b][c] + 1
g[na][nb][nc] = 1
for i in range(h):
for j in range(n):
for k in range(m):
if check[i][j][k] == -1 and g[i][j][k] == 1:
bfs(i, j, k)
ans = 0
notall = False
for i in range(h):
for j in range(n):
for k in range(m):
if g[i][j][k] == 0:
notall = True
else:
ans = max(ans, check[i][j][k])
if notall:
print(-1)
else:
print(ans)
처음에 틀린 코드
이유 : 영향을 받아서 익는게 동시에 일어난다고 생각해야하는데 순차적으로 일어난다고 코드를 짜서 틀림 (bfs 돌릴 때 기존의 토마토가 있던 곳은 한번에 넣고 동시에 탐색해야한다)
반례 )
3 3 1
1 1 0
0 0 0
0 0 0
정답 : 3 내 출력 : 4
from collections import deque
dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, -1, 1]
m, n, h = map(int, input().split())
g = []
for i in range(h):
tmp_g = [list(map(int, input().split())) for _ in range(n)]
g.append(tmp_g)
check = [[[-1] * m for _ in range(n)] for _ in range(h)]
def bfs():
q = deque()
for i in range(h):
for j in range(n):
for k in range(m):
if check[i][j][k] == -1 and g[i][j][k] == 1:
check[i][j][k] = 0
q.append((i, j, k))
while q:
a, b, c = q.popleft()
for d in range(6):
na, nb, nc = a + dx[d], b + dy[d], c + dz[d]
if 0 <= na < h and 0 <= nb < n and 0 <= nc < m:
if check[na][nb][nc] == -1 and g[na][nb][nc] == 0:
q.append((na, nb, nc))
check[na][nb][nc] = check[a][b][c] + 1
g[na][nb][nc] = 1
bfs()
ans = 0
notall = False
for i in range(h):
for j in range(n):
for k in range(m):
if g[i][j][k] == 0:
notall = True
else:
ans = max(ans, check[i][j][k])
if notall:
print(-1)
else:
print(ans)
수정 코드 : 기존의 토마토들은 한번에 큐에 넣었다. 이 부분 꼭 주의해서 논리적 오류 없애기