[Programmers 1844]ゲームマップ最短距離(Python)



質問する


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

これは[0,0]の1段目で[n,m]の格子に移動できる最短距離の問題である.
移動できない場合は、-1を出力します.
定置期とグループ投影は、アルゴリズムを作るためにしばらく休んだが、結局忘れてしまった.
大変なことになった.⸝⸝ʚ̴̶̷̆_ʚ̴̶̷̆⸝⸝ ,, .. ,

問題を解く

  • の範囲で上下左右に移動し、路(1)を双方向図とする.
  • 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