[프로그래머스 | DFS/BFS] 게임 맵 최단거리 Python

효율성 테스트가 관건인 문제.
최단거리를 구하는 문제이니, DFS보다는 BFS로 풀어야 함.
DFS 이용하면 정답은 나오지만, 효율성 테스트에서 실패한다!

def solution(maps):
    MAX = 100000
    move = [
        [1, 0], 
        [0, 1], 
        [-1, 0],
        [0, -1] 
    ]
    
    rows = len(maps)
    cols = len(maps[0])
    
    dist = [[MAX]*cols for _ in range(rows)]
    dist[0][0] = 1
    
    from collections import deque
    route = deque([[0, 0]])
    
    length = 0
    # while route and dist[rows-1][cols-1]==MAX:
    while route:
        cur_r, cur_c = route.popleft()
        for dr, dc in move:
            new_r = cur_r + dr
            new_c = cur_c + dc
            if 0<= new_r < rows and 0<= new_c < cols and maps[new_r][new_c]==1 and dist[new_r][new_c] > dist[cur_r][cur_c]+1:
                dist[new_r][new_c] = dist[cur_r][cur_c]+1
                route.append([new_r, new_c])
    
    answer = dist[rows-1][cols-1] if dist[rows-1][cols-1]!=MAX else -1
    return answer

route.popleft()를 route.pop()로 바꾸면 DFS 풀이가 됨.
하지만, DFS로 풀면 map 크기가 커졌을 때 시간이 오래 걸리게 됨.

BFS로 풀면 효율적인 이유?
DFS를 이용하면, 어느 루트가 최단거리가 될 지 모르기 때문에 모든 경우의 수를 다 살펴보아야 함. 반면, BFS를 이용하면 길찾기 과정 중 이미 이 경로보다 짧은 경로가 있다면 즉시 탐색을 중단함.