ラビリンス最短パスDFSとBFSの比較

1.問題の理解

<ソース:https://programmers.co.kr/learn/courses/30/lessons/1844#qna>
これは簡単な問題です.(1,1)から対角線末端(n,m)までの最短経路の解法問題.符号化テストを学んだ人は、dfs、bfsを思い出すことがあります.これはよくある問題です.しかしここでdfsとbfsを考えると、少し勉強をおろそかにしている人と言えるでしょう.
はい、それは私です.
これらの問題で混同されないように、このように記録を残します.
2.初回試行、、DFS

import copy
import sys

def dfs(maps,cur,pre_visited,depth) : 
    global dist, row, col
    x,y = cur
    visited = copy.deepcopy(pre_visited)
    visited[x][y] = 1
    if cur == (row-1,col-1) :
        dist = min(dist,depth)
        return
    for dx,dy in (-1,0) , (0,1) , (1,0) , (0,-1) : #위 , 오, 아 ,왼 
        nx,ny = x+dx,y+dy
        if (0 <= nx <  row) and (0 <= ny < col) and maps[nx][ny] != 0 and visited[nx][ny] != 1 and depth+1 < dist :
            dfs(maps,(nx,ny),visited,depth+1)
    
def solution(maps):
    sys.setrecursionlimit(10**7)
    global dist, row, col
    dist = 10**8
    row  = len(maps)
    col = len(maps[0])
    visited = [[0]*col for _ in range(row)]
    dfs(maps,(0,0),visited,1)
    return -1 if dist == 10**8 else dist

最初の試みはdfsです.
私の考えはdfsですべての経路を探求することで、もしすべての経路に長さがあれば、これが最小の経路であることを確認して、ほほほ
今书きながら考えるとどんなに短い想いだろう...
dfsで解くと答えが出てきます!しかし、効率的なテストの問題であれば、この方法は10000%失敗します.
3.じゃあ?BFSは
実は最短経路問題の定式はbfsです.一度アクセスしたノードは再アクセスする必要がないからです.そして目的地に着いた瞬間、他のルートを考える必要はありません.その経路が最短経路だからです.
下図に示すように,DFSとBFS法を用いて最短経路を解く場合の効率が考えられる.

1番格子のところは道で、ないところは壁です.
サブdfsを使用してナビゲーションを行う場合、どのくらいのノードにアクセスする必要がありますか?
dfs:4+13*3**2+1+4.
ここからdfsの問題がわかる.分岐点が出るたびに、突き当たりまで行って、それから分岐点に戻ります...
では、今のように2つではなく1000の三叉路があるとしたら?
dfs : 4 + 13 * 3 **1000 + 1000 + 4
13*3の1000勝はははは...時間の複雑なグラフィックでは非効率といえる.
逆にbfsは?すべてのノードにアクセスするだけで簡単です.
bfs:4+13*2+1+4.
これも、上図でbfsの三叉路1000個の迷路にナビゲートすると
bfs:4+13*1000+1000+4.
やっぱり!数字で感じるのが一番早いようです.ほほほ
このように,最短経路問題ではbfsがdfsよりも効率的に答えを求めるようである.
答えが見つからないわけではない.有効なものが見つからないだけ!
4.BFS閲覧時の注意事項!
(1)

    while queue :
        x,y,depth = queue.popleft()
        visited[x][y] = 1
        if (x,y) == (row-1,col-1) :
            return depth
        for dx,dy in (1,0),(0,1),(0,-1),(-1,0) :
            nx,ny = x+dx,y+dy
            if 0<=nx<row and 0<=ny<col and /
            maps[nx][ny] != 0 and visited[nx][ny] ==0 :
                queue.append((nx,ny,depth+1))

(2)

    visited[0][0] = 1
    while queue :
        x,y,depth = queue.popleft()
        if (x,y) == (row-1,col-1) :
            return depth
        for dx,dy in (1,0),(0,1),(0,-1),(-1,0) :
            nx,ny = x+dx,y+dy
            if 0<=nx<row and 0<=ny<col and /
            maps[nx][ny] != 0 and visited[nx][ny] ==0 :
                visited[nx][ny] = 1
                queue.append((nx,ny,depth+1))

(1)番号と(2)番号の違いは何ですか.
どこでアクセスチェックをするかで違います!
では、より効率的なコードとは何でしょうか.
同様に、この2つの問題の答えはいずれも現れる可能性がある.しかし(1)回の場合は,bfs特性をうまく表現していないコードといえる.
キューでpopを実行して領域にアクセスした場合、問題は何ですか?
例を挙げる.
AとBが同じ幅の現在のキュー内のノードである場合、まずAをポップアップし、アクセスします.BがAから接続されたノードにある場合、Bはキューにありますが、アクセスされていないノードなので、キューに繰り返し入れます.そうであれば、bfsの特徴はノード数で繰り返すことであり、重複ノードにアクセスする場合がある.
同じ答えを出すコードでも、概念をより効率的に理解する必要があります...
5.DFS、BFS応用/利用率の問題を解決する:
DFS、BFSは、その特徴により、より使いやすい問題タイプがある.
グラフィック内のすべての頂点にアクセスすることが主な問題です.
すべての頂点にのみアクセスする重要な問題については、DFSとBFSの2つの方法のいずれかを使用することができます.

パスフィーチャーを格納する必要があるという問題です.たとえば、各頂点に数字がある、aからbまでのパスを解く、パスに同じ数字がないなど、パスごとにフィーチャーを格納する必要がある場合はDFSを使用します.(BFSは経路機能を備える)

.

最短距離の問題
迷路など最短距離を探す必要がある場合はBFSが有利です.
深度優先パスを使用すると、最初に検出された答えは最短距離ではないかもしれませんが、幅優先検索は現在のノードに近い場所から検索されるため、パスを検索するときに最初に見つけられる答えは最短距離です.

それ以外は
検索するグラフィックが非常に大きい場合、DFSを考慮したグラフィックは

です.

検索対象の規模が大きくなく、検索開始点から遠くない場合は、BFSを考慮することが望ましい.