문제 링크
https://www.acmicpc.net/problem/7569
구현
사실 보기에는 어려워보이기는 하는데, 생각을 3차원으로 확장시키면 여타 BFS문제와 다를 것이 없다. 문제에서 각 $m$, $n$, $h$가 모두 100까지라고 명시하고 있다. $100 \times 100 \times 100 = 1,000,000$ 이므로, 3차원 리스트에 할당해버려도 큰 문제가 없다고 생각했다.
시작할 때 1인 지점들을 먼저 queue에 넣어두고, 여타 문제에서 하던 상하좌우 체크에서 높이 +1, -1을 추가해주면 된다.
다만 내가 푼 코드는 시간이 좀 오래걸린 것 같다. 시간이 적게 나온 코드들을 좀 살펴봐야겠다.
코드
from sys import stdin
from collections import deque
input = lambda : stdin.readline()
def main():
m, n, h = map(int, input().split())
farm = list()
for _ in range(h):
tmp = list()
for __ in range(n):
tmp.append(list(map(int, input().split())))
farm.append(tmp)
queue = deque()
for i in range(h):
for j in range(n):
for k in range(m):
if farm[i][j][k] == 1:
queue.append([(i, j, k), 0])
while queue:
node = queue.popleft()
for i, j in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
new_x, new_y = j + node[0][2], i + node[0][1]
if 0 <= new_x < m and 0 <= new_y < n:
if not farm[node[0][0]][new_y][new_x]:
farm[node[0][0]][new_y][new_x] = 1
queue.append([(node[0][0], new_y, new_x), node[1] + 1])
for k in [-1, 1]:
new_z = node[0][0] + k
if 0 <= new_z < h:
if not farm[new_z][node[0][1]][node[0][2]]:
farm[new_z][node[0][1]][node[0][2]] = 1
queue.append([(new_z, node[0][1], node[0][2]), node[1] + 1])
for i in range(h):
for j in range(n):
for k in range(m):
if not farm[i][j][k]:
print(-1)
return
print(node[1])
if __name__ == '__main__':
main()