https://www.acmicpc.net/problem/7576
나의 풀이
from collections import deque
import sys
input = sys.stdin.readline
M, N = map(int, input().rstrip().split())
def result_check(map_list, ct):
for i in range(N):
for j in range(M):
if map_list[i][j] == 0:
return -1
return ct
map_list = []
queue = deque()
for i in range(N):
now_list = list(map(int, input().rstrip().split()))
map_list.append(now_list)
for j in range(M):
if now_list[j] == 1:
queue.append((i,j))
ct = 0
while queue:
next_queue = deque()
while queue:
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 (map_list[n_a][n_b] == 0):
map_list[n_a][n_b] = 1
next_queue.append((n_a, n_b))
if next_queue:
ct += 1
queue = next_queue
else:
break
print(result_check(map_list, ct))
시간 복잡도
BFS로 모든 경로를 탐색 하므로 ( 이차형 시간 복잡도 )
해당 알고리즘 시간복잡도는 : 이차형 시간 복잡도 ( O(n**2) )
