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

상하좌우로 이동할 수 있는 맵에서 특정한 지점에서 어느 지점까지 이동하는데 최단 거리를 구해야된다는 문제였고, 이는 BFS를 이용해 이전 위치에 다음 위치를 더해 이동한 위치마다 시작점으로부터의 거리를 나타내어 풀 수 있었던 아이디!
어를 떠올렸다.

기억해야될 점은 큐자료구조를 이용하기 위해 파이썬의 deque를 임포트해서 사용할 때, deque안에 매개변수로 리스트를 넣어 객체를 만들어 사용한다는 점을 까먹지 말아야겠다. 또한 어제 정렬문제인 카드 정렬하기 문제를 풀 때, heapq를 사용하였는데, 이는 따로 객체를 생성하지 않고 파이썬 리스트를 heapq 매개변수로 넣어 데이터를 삽입하고 꺼내는 동작을 하여서 BFS의 deque 사용방법과 헷갈리지 말아야할 것이다.

# 미로찾기나 상하좌우맵에서 최소이동거리 => BFS이용해서 이전 위치에 1씩 더하기
from collections import deque

def solution(maps):
    answer = 0
    n = len(maps)
    m = len(maps[0])
    
    # 상하좌우 방향벡터
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]
    queue = deque([(0,0)])
    while queue:
        pos = queue.popleft()
        r = pos[0]
        c = pos[1]
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < n and 0 <= nc < m and maps[nr][nc] == 1:
                maps[nr][nc] += maps[r][c]
                queue.append((nr, nc))
    answer = maps[n-1][m-1]
    if answer == 1:
        return -1
    return answer