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

queue 를 이용한 BFS 문제이다. 

자세한 설명은 주석을 통해..

from collections import deque

def solution(maps):
    
    row = len(maps)
    col = len(maps[0])
    
    dx = [-1, 1, 0, 0] # col 증가는 오른쪽으로 증가
    dy = [0, 0, -1, 1] # row 증가는 아래쪽으로 증가
    
    graph = [[-1 for _ in range(col)] for _ in range(row)] # 이동 칸 수를 기록하기 위한 그래프
    
    q = deque()
    q.append([0,0]) # 시작위치
    
    graph[0][0] = 1 # 시작점은 그자체로 1칸 이동한 것으로 침.
    
    while q:
        y, x = q.popleft() # 행, 열로 탐색할 것이기 때문에 y, x로 출력.
        
        # 방향 탐색
        for i in range(4):
            ny = y + dy[i] # 가려고하는 행
            nx = x + dx[i] # 가려고하는 열
            
            
            if 0 <= ny < row and 0 <= nx < col and maps[ny][nx] == 1:
            # 가려고하는 위치가 맵을 벗어나지 않고 장애물이 아닐 때.
                if graph[ny][nx] == -1: # 처음 가는 곳이면
                    graph[ny][nx] = graph[y][x] + 1 # ex) 시작위치가 1이므로 다음으로 갈 수 있는 위치는 2가 됨.
                    q.append([ny, nx]) # queue 에 다음위치를 추가하여 while 시작할 때 이곳에서부터 다시 탐색하도록.
                    
    answer = graph[-1][-1] # 도착위치의 이동수
    return answer