https://www.acmicpc.net/problem/7569
나의 풀이
from collections import deque
import sys
input = sys.stdin.readline
M, N, H = map(int, input().rstrip().split())
def result_check(floor_dict, ct):
for fk in floor_dict.keys():
for i in range(N):
for j in range(M):
if floor_dict[fk][i][j] == 0:
return -1
return ct
floor_dict = {}
queue = deque()
for i in range(H):
n_list = []
for j in range(N):
n_list.append(list(map(int, input().rstrip().split())))
for idx in range(M):
if n_list[j][idx] == 1:
queue.append((i, j, idx))
floor_dict[i] = n_list
# 탐색 시작
ct = 0
while queue:
next_queue = deque()
while queue:
i, a, b = queue.popleft()
for m_a, m_b in ((1,0),(-1,0),(0,1),(0,-1)):
n_a, n_b = a+m_a, b+m_b
if (0 <= n_a < N) and (0 <= n_b < M) and (floor_dict[i][n_a][n_b] == 0):
floor_dict[i][n_a][n_b] = 1
next_queue.append((i, n_a, n_b))
for m_h in (1,-1):
n_h = i+m_h
if (0 <= n_h < H) and (floor_dict[n_h][a][b] == 0):
floor_dict[n_h][a][b] = 1
next_queue.append((n_h, a, b))
if next_queue:
ct += 1
queue = next_queue
else:
break
print(result_check(floor_dict, ct))
시간 복잡도
3차원의 BFS를 탐색 하므로 ( 삼차형 시간 복잡도 )
해당 알고리즘 시간 복잡도는 : 삼차형 시간 복잡도 ( O(n**3) )
