DFS/BFS

🏀 概要
アルゴリズムの探索部分を学びたいです.
まだ多くのコードテストを経験していませんが、探求問題は毎回現れると思います.
もちろん、ナビゲーションの種類は多いですが、今回はDFS/BFSについて知ります.
注意:
これは東彬またはYouTubeチャンネルをベースに整理されていますので、YouTubeリンクを添付します.
YouTubeにリンク
💡 方法
まず、DFS/BFSを理解するには、スタック、キュー、および再帰関数を理解する必要があります.再帰関数は、DFSの深さを確保するために使用され、スタックはDFSにも使用され、キューはBFSにも使用されます.
デフォルトでは、使用する構成は、ノード間の関係を示す図、アクセスの有無を確認するアクセスリスト、各基準に基づいて使用されるスタックおよびキューです.それぞれの要因を理解してみましょう.
graph
隣接ノード情報を二重リスト形式で伝える資料構造と考えられる.現在、幹線の重みは同じで、考慮しない図形と考えられる.
[
[],#図0はノードの始点が1であるため空であることを示す.
［2,3,8］,＃1のノードは2,3,8のノードに接続されていると理解できる.
[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]#は上記と同様に理解できる
]
画像を見せてくれて理解に役立つけど...パス.ははは
visited list
アクセス=[False]*len(図)#各ノードの部屋をチェックします.
図面の参照を続行するには、スタックとキューからインポートされたノードにアクセスするかどうかを確認する必要があります.
一般

if visited[i] == False:
	dfs(g,i,visited) or bfs(g,i,visited) 

このように使うのがいいと理解しています.
スタックやキューについては、いろいろな方法で理解できるので、ここで説明するつもりはありません!
💎 DFS
深度優先度ナビゲーション.すなわち、隣接ノードを参照する基準を深さと参照として位置づけることができる.stackを使用してこの深さを保証します.
最もコアな要素、深さがノードに優先的にアクセスする方法を説明しようとします.
前述したように、隣接ノード情報は、各ノードを遍歴するため、繰り返し文でグラフィックにアクセスする必要があることを図に示している.

for i in graph[v]:
	if not visited[i]:
    		dfs(graph,i,visited)

vは、パラメータに開始点として渡されます.
すなわち,始点に隣接するノードリストを受信し,巡回として深さ優先アクセスが可能である.
この部分が理解できない場合は,再帰関数の作用原理を考慮して,もう一度見ると理解に役立つ.
コアではなく全体的なコードから見ると、

def dfs(graph,v,visited):
	visited[v] = True # 방문 처리
    	print(v, end = " ") # 순서를 보여주기 위한 출력
    	for i in graph[v]: # 인접노드리스트 받아오기
    		if not visited[i]: # 방문 안한 경우에만 방문하도록
        		dfs(graph,i,visited) # 깊이를 우선하기 위해서 재귀 함수 사용!

このようにdfs(graph,1,accessed)を実行すると、1 2 7 6 8 3 4 5と呼ばれる結果値が生成される.
💎 BFS
ナビゲーション幅の優先度は、上の図と同じですが、同じ深さのノードを優先ナビゲーションと見なしてください.これを保証するために、同じ深さノードをキューで管理します.
主な特徴は,幹線の重みが等しい場合,ノード間の最短距離を探すのに適していることである.その理由は,すべてのノードに対して距離を計算するため,最短距離が分かるからである.
BFSがコードで表示されます

def bfs(graph, start, visited):
	queue = deque[(start)] # 같은 depth를 보장하기 위해서
    visited[start] = True
    while queue: # queue를 통해 모든 노드를 순회하기 위함
    	v = queue.popleft()
        print(v, end = " ")
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True # 방문 처리
                

最終的には,目的を達成するためにデータ構造や再帰関数を用いて順序を保証し,全体処理はアクセス処理である.
🔧 例題
この方法を理解し、このツアーをどう使うか考えました.
基本的にはナビゲーションに基づいています.
1.すべてのノードを問い合わせる
2.グラフィック形式、すなわち2 Dリスト
パレードオブジェクトのグラフィックが上記で仮定した隣接ノード情報でない場合は、x、y座標でノードが隣接しているかどうかを知ることができ、ノードがアクセス可能かどうかを知っている場合は、多くの場所で使用できます.
例示的な問題の説明は、上記のYouTubeで確認できます.私がこの問題を書いた気持ち
私が作ったコードを下に添付するつもりです.
冷たい飲み物

def dfs(graph,x,y):
    n = len(graph)
    m = len(graph[0])
    
    if x < 0 or x >= n:
        return False
    if y < 0 or y >= m:
        return False
    
    if graph[x][y] == 0: # 각 값은 방문 가능 상태 
        # x,y를 통해 인접노드, 상하,좌우 모두 방문하여 상태값 변경
        dfs(graph,x+1,y)
        dfs(graph,x-1,y)
        dfs(graph,x,y+1)
        dfs(graph,x,y-1)
        return True # 접근 가능한 모든 노드를 방문하고 종료
    return False # 일단 방문이 안한다면 의미가 없다.

if __name__ == '__main__':
    n, m = map(int,input().split())
    graph = []
    for i in range(n):
        graph.append(list(map(int,input())))
    result = 0
    # 그래프 순회
    for i in range(n):
        for j in range(m):
            if dfs(graph,i,j) == True: # True 면 한 블럭에 대해서 다 처리 했다. 즉 , result를 1만큼 증가해라
                result += 1
    print(result)