グリッド上の 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 / 13
訪問済み
0
フロンティア
1
現在
—
0 / 13
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 / よくある落とし穴
i.
訪問済みにするタイミングを間違える。
セルを訪問済みにするのはエンキューする瞬間であり、ポップ時ではない —— そうでないと、処理される前に同じセルを何度も押し込んでしまう。 BFS では最短路の不変条件が崩れ、いずれにせよメモリも膨らむ。
ii.
順序が重要な場面で BFS と DFS を取り違える。
無重みグラフ上の最短路問題には BFS が必要。 DFS は最短路を出さない —— 一方向に進み切って、行き止まりで初めて戻るからだ。
iii.
DFS の再帰の深さ。
1000×1000 のグリッド上で再帰 DFS を回すと、1 本の長いパスでコールスタックが溢れることがある。 大きな入力では明示的なスタックに切り替えるか、BFS で済むならそちらを使う。
05 / LeetCode で練習
4 問。最初の 2 問は基本のフラッドフィル / 到達可能性、3 問目は多始点 BFS、 4 問目は同じアルゴリズムを暗黙的グラフに持ち上げる。