グリッド上の BFS / DFS
01 / 一文で言うと
種から暗黙的なグラフを歩き、エンキューと同時にセルを訪問済みにする —— キューなら幅(最も近い順)、 スタックなら深さ(一方向に進み切る順)。残りは同じアルゴリズム。
問題(r, c) から 4 近傍隣接でフラッドグリッド4 × 4開始(0, 0)モードbfs
1
1
1
1
1
·
·
1
1
·
·
1
1
1
1
1
キュー (1)
(0,0)
← 先頭(0,0) から開始。キューを種セルで初期化。
ステップ
0 / 61
訪問済み
0
フロンティア
1
現在
—
0 / 61
02 / パターンの骨格
# (sr, sc) からフラッドvisited ← {(sr, sc)}frontier ← [(sr, sc)]while frontier が空でない:cell ← frontier. pop_front() // BFS// または frontier.pop() // DFSfor cell の 4 近傍について:if 範囲内・通行可・ 未訪問:訪問済みにする;frontier に押し込む
03 / このパターンを使うべき合図
「グリッド / マップ」
隣接関係を持つ 2 次元レイアウトを扱う問題 —— 島、迷路、腐ったオレンジ、壁と通路。
「最短 / 最少」
始点からの距離が必要 —— 最小ステップ数、最少移動数。BFS が一度のパスで答えを出す。層ごとに広がるからだ。
「到達可能 / 連結」
どのセルが到達可能かだけが必要で、順序は問わない —— どちらの探索でもよい。 DFS は再帰で書くと通常はより簡潔。
「暗黙的グラフ」
「頂点」はあらかじめ作られているわけではない —— 状態(位置、盤面)であり、 後継関数によって遅延的に生成される。アルゴリズムは同じで、変わるのは近傍関数だけ。
04 / よくある落とし穴
訪問済みにするタイミングを間違える。
セルを訪問済みにするのはエンキューする瞬間であり、ポップ時ではない —— そうでないと、処理される前に同じセルを何度も押し込んでしまう。 BFS では最短路の不変条件が崩れ、いずれにせよメモリも膨らむ。
順序が重要な場面で BFS と DFS を取り違える。
無重みグラフ上の最短路問題には BFS が必要。 DFS は最短路を出さない —— 一方向に進み切って、行き止まりで初めて戻るからだ。
DFS の再帰の深さ。
1000×1000 のグリッド上で再帰 DFS を回すと、1 本の長いパスでコールスタックが溢れることがある。 大きな入力では明示的なスタックに切り替えるか、BFS で済むならそちらを使う。
05 / LeetCode で練習
中級32
01Word Search— LC 79→02Surrounded Regions— LC 130→03Clone Graph— LC 133→04Number of Islands— LC 200→05Course Schedule— LC 207→06Course Schedule II— LC 210→07Graph Valid Tree— LC 261→08Walls and Gates— LC 286→09Number of Connected Components in an Undirected Graph— LC 323→10Evaluate Division— LC 399→11Pacific Atlantic Water Flow— LC 417→12Minimum Genetic Mutation— LC 433→1301 Matrix— LC 542→14Number of Provinces— LC 547→15Max Area of Island— LC 695→16Open the Lock— LC 752→17Is Graph Bipartite?— LC 785→18All Paths From Source to Target— LC 797→19Keys and Rooms— LC 841→20Possible Bipartition— LC 886→21Snakes and Ladders— LC 909→22Shortest Bridge— LC 934→23Rotting Oranges— LC 994→24Number of Enclaves— LC 1020→25Shortest Path in Binary Matrix— LC 1091→26Shortest Path with Alternating Colors— LC 1129→27As Far from Land as Possible— LC 1162→28Path with Maximum Gold— LC 1219→29Number of Closed Islands— LC 1254→30Number of Operations to Make Network Connected— LC 1319→31Count Sub Islands— LC 1905→32Maximum Number of Fish in a Grid— LC 2658→
難しい11
01Word Ladder II— LC 126→02Word Ladder— LC 127→03Word Search II— LC 212→04Number of Islands II— LC 305→05Longest Increasing Path in a Matrix— LC 329→06Reconstruct Itinerary— LC 332→07Robot Room Cleaner— LC 489→08Bus Routes— LC 815→09Making A Large Island— LC 827→10Unique Paths III— LC 980→11Shortest Path in a Grid with Obstacles Elimination— LC 1293→