[ Programmers 1844 ] 게임 맵 최단거리(Python)

문제

https://programmers.co.kr/learn/courses/30/lessons/1844

[0,0]번째칸에서 [n,m]칸으로 이동할 수 있는 최단 거리를 구하는 문제다.
이동할 수 없으면 -1을 출력하면 된다.

정처기랑 플조조 플젝,, 하느라 알고리즘 좀 쉬었더니 다 까먹었따.
큰일났다. ⸝⸝ʚ̴̶̷̆_ʚ̴̶̷̆⸝⸝ ,, .. ,

문제 풀이

1. 범위 내의 상하좌우로 이동하면서 길(1)이면 양방향 그래프로 이어주었다.
2. bfs를 이용해 갈 수 있는 모든 길을 갈 것이다.
   2-1. deque에 [(좌표), 이동한 칸의 수] 를 넣어준다.
   2-2. 이동 가능한 경로로 모두 이동하다가 도착지에 도착했을 때 가장 짧은 칸의 수를 출력해주면 된다.

코드

from collections import deque
from collections import defaultdict

def solution(maps):
    n = len(maps)
    m = len(maps[0])
    
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    
    graph = defaultdict(list)
    for i,row in enumerate(maps):
        for j,check in enumerate(row):
            if check == 1:
                for k in range(4):
                    nx = i + dx[k]
                    ny = j + dy[k]
                    if 0 <= nx < n and 0 <= ny < m:
                        if maps[nx][ny] == 1:
                            graph[(i,j)].append((nx,ny))
                            graph[(nx,ny)].append((i,j))
   
    def bfs(graph,i,j):
        visit = [[0] * m for _ in range(n)]
        visit[0][0] = 1
        queue = deque()
        queue.append([(i,j),1])

        while queue:
            temp = queue.popleft()
            location, cnt = temp[0], temp[1]
            if location == (n-1,m-1):
                return cnt
	    # 방문 안한 좌표일 때만 체크해준다.
            if location not in visit:
                x, y =location[0], location[1]
                visit[x][y] = 1
		#인근 좌표에 대해서 방문을 해준다.
                if location in graph:
                    next_nodes = list(graph[location])

                    for next_node in next_nodes:
                        x, y =next_node[0], next_node[1]
                        if visit[x][y]== 0:
                            queue.append([next_node,cnt+1])
                            visit[x][y] = 1
    
    answer = bfs(graph,0,0)
    if (answer): return answer
    return -1