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

"""
최단거리 -> 다익스트라, BFS

다익스트라 -> 간선에 가중치가 있을때
BFS -> 가중치가 모두 1일때 효율적

가중치가 음수일땐 벨만-포드 고려

동서남북 중 갈수 있는 곳 Q에 넣어줌 
최소로 도착한다는게 결국 모든 경로를 탐색할 필요가 없는것

가다 막히는 경로는 알아서 pop 되며 소실 될거고
많이 뻣어나가는 경로중 가장 일찍 도착하는 하나만 보면 되는거임 

"""
from collections import deque
def bfs(maps):
    pos = [0,0]
    goal = [len(maps)-1,len(maps[0])-1]
    path = deque([(pos,1)])
    visited = [[False for _ in range(len(maps[0]))] for _ in range(len(maps))]
    # 우 상 좌 하
    move = [[0,1],[1,0],[0,-1],[-1,0]]
    
    visited[0][0] = True
    while path:
        pos,cnt = path.popleft()
        if pos == goal:
            return cnt
        
        for dx, dy in move:
            nx, ny = pos[0] + dx, pos[1] + dy
            
            if 0 <= nx < len(maps) and 0 <= ny < len(maps[0]) and not visited[nx][ny] and maps[nx][ny] == 1:
                path.append(([nx, ny], cnt + 1))
                visited[nx][ny] = True  # 방문 처리
            
    return -1
             
def solution(maps):
    answer = bfs(maps)
    return answer