[プログラマー]ゲームマップ最短距離

この問題は典型的なBFS問題である.確かにBFSで解決したのですが、BFSは知らないと思います.問題では最小距離を求めることが求められているが,BFS自体は来た道に戻っていないため,最小距離を保証できる.

1.問題の説明

これらの指導があれば、以下の方法があるかもしれません.このとき、一番下のパスのうち、一番目のパスが一番小さいパスになります.


この場合、通過する経路の重み付け値がいずれも1であれば、最小重み付け和を求めればよい.

2.難しいところ

1）最小長さをBFSに設定

BFSは完全なナビゲーションであり、私が考えているBFSはキューにポイントを配置し、隣接するすべてのポイントにナビゲートします.だからこれは最低限ではないと思います.
上図では、第1の例と第2の例ではカウントが異なるので、この2つの例はいずれも最小値の条件を満たしていると思います.第2の例では、第1のアクセスポイントが再アクセスされているため、候補として使用できません.
以前に訪問したポイントを再訪問しないことは、最小限の条件を満たしています.

2）重み付け隣接行列

BFSを解くには,アクセス重みの和を求める隣接行列を別途設定する必要がある.この技法は私には使えないようだ.
以前は距離を確認してもこのように問題を表現していたが、当時とは違って、最初は表現されていなかったような気がした.
これからは、その意味をしっかり把握し、運用しなければなりません.

3.解答

    #일단 전체 길에 포함여부 확인
    #이미 갔던 길은 다시 들어가면 노노링 
    #현재 위치에서 상하좌우를 확인하되, 해당 위치가 0이면 안됨
from collections import deque

def solution(maps):
    confirm_point = [(-1,0),(1,0),(0,-1),(0,1)] #dy, dx
    queue = deque()
    queue.append((0,0))
    graph = [[-1 for _ in range(len(maps[0]))] for _ in range(len(maps))]
    graph[0][0] = 1
    
    while queue:
        start_point = queue.popleft()
        for dy, dx in confirm_point:
            y = dy+start_point[0]
            x = dx+start_point[1]
            
            if -1<y<len(maps) and -1<x<len(maps[0]) and maps[y][x]==1: #전체 map에 포함되는지?
                if graph[y][x] ==-1:
                    graph[y][x] = graph[start_point[0]][start_point[1]] + 1
                    queue.append((y,x))
    
    ## 막혔던 점
    ## 2갈래가 나뉘어지면, 이후에는 어떻게 갈라서 코드를 작성할지 몰랐음 
    ## 2갈래로 나눠 진다는 생각 자체가 잘못됨, 이미 앞에서부터 탐색 후 방문된 점을 돌았기 때문에 ...
    ## 그걸 graph가 해줌
    ## 인접행렬(graph)를 선언
    
    return graph[-1][-1]