미로 탐색

2178번: 미로 탐색

 

나의 풀이

from collections import deque
import sys
input = sys.stdin.readline

n,m = map(int, input().rstrip().split())

map_list = []
for _ in range(n):
    map_list.append(list(map(int, input().rstrip())))

queue = deque([(0,0)])
while queue:
    a,b = queue.popleft()
    
    for m_a, m_b in ((1,0),(-1,0),(0,1),(0,-1)):
        new_a, new_b = a+m_a, b+m_b
        if (0 <= new_a < n) and (0 <= new_b < m) and (map_list[new_a][new_b] == 1):
            map_list[new_a][new_b] = map_list[a][b] + 1
            queue.append((new_a, new_b))
print(map_list[-1][-1])

 

 

시간 복잡도

while queue : dfs 알고리즘으로 모든 노드를 순회하므로 ( 이차형 시간 복잡도 )
해당 알고리즘 시간복잡도는 : 이차형 시간 복잡도 ( O(n**2) )