DFS / BFSとは
- Wikipedia - 深さ優先探索（Depth-First Search、DFS、バックトラック法）
- Wikipedia - 幅優先探索（Breadth-First Search、BFS）
Wikipediaにはなんだか難しそうな事が書いてありますが、「経路を順にたどってゴールに到達するような問題」「ルールに基づいて一定範囲を塗りつぶすような問題」を実装する際に役に立つアルゴリズムです。迷路を解くとか一定エリアの広さを考えるといった問題が出てきたらまずはこの DFS / BFS が適用可能かどうか考えてみると良い 1 と思います。
「知らないと詰む」系のアルゴリズムですし、知ってると気持ちよく解ける 2 のでぜひ DP（動的計画法）の前にこちらを使い倒せるようにしてください。
迷路のような典型的な問題であればすぐに DFS / BFS を思いつくのですが、塗りつぶしや領域判定でこれが使えることは慣れないと思いつきにくいです。
実装イメージ
実装にあたって用意するものは下記の2点です。
- 探索候補地点を格納する「探索候補スタック」
- 探索済み地点を格納する「探索済みリスト」
これらを使って、DFS を組む時の具体的なロジックイメージは下記の通りです。※BFS を組む場合は「候補探索スタック」を「候補探索キュー」に、pop を pop(0) もしくは popleft（collections.deque の場合）に読み替えてください
探索スタート地点を「探索候補スタック」に積む
while スタックが空っぽになるまで
スタックから次の探索地点を1つ取り出す（pop）
「探索済みリスト」に取り出した地点を格納（ここが現在地点）
現在地点から、次に行こうと思えば行けるポイントを全部探し出す
for 地点 in 次に行こうと思えば行けるポイント
if その地点は既に「探索済みリスト」にある？
探索済みなので「探索候補スタック」には入れない（continue）
if その地点は既に「探索候補スタック」にある？（閉路があるなら可能性あり、木なら可能性なし）
探索予定なので「探索候補スタック」には入れない（continue）
未探索かつ候補にも入っていない地点なので「探索候補スタック」に追加する（append）
print 探索済み地点
これをブン回せば、最後に出てくる「探索済みリスト」が探索の足跡を全部記録してくれています。
塗りつぶし面積などを求めたい場合はこうやってDFSすると探索の足跡サイズ（配列の大きさ）がそのまま面積になりますし、迷路の最短経路を求めたい場合は上記をキューに変更してBFSするとゴールまでの最短距離が分かります（ゴールに到着した瞬間に break）
DFS は再帰で実装する例もよく紹介されますが、個人的には DFS だろうと BFS だろうと同じロジックで実装できる、上記の「空っぽになるまで while でブン回す」方がシンプルでオススメです。
【重要】なんでこれでできるの？
DFS / BFS の手法によってなぜ経路探索が無駄なく実現できるのか、なぜスタックだと深さ優先でキューだと幅優先が実現されるのかについては、ぜひ頭の中できちんと理解をしておいてください。特に「探索済みリスト」と「探索候補スタック」がどのように変化していくのかを 1 ステップ 1 ステップ理解することが重要です。
というわけで、上記のような地図を、1 から 6 まで DFS で辿る動きを追ってみましょう。ロジックイメージと地図を横に置いて、下記を読み進めてみてください。
while 1 ループ目（終了地点）
- 現在位置：1
- 探索済みリスト：( 1 )
- 探索候補スタック：( 2, 5 )
スタート地点として「探索候補スタック」に積まれていた 1 が pop され、探索済みリストに格納されます。あわせて 1 から移動する先の候補として 2 と 5 が「探索候補スタック」に積まれます。
while 2 ループ目（終了地点）
- 現在位置：5
- 探索済みリスト：( 1, 5 )
- 探索候補スタック：( 2, 4 )
「探索候補スタック」の一番後ろから 5 が pop され、探索済みリストに格納されます。5 から移動する先の候補は 1 と 2 と 4 ですが、1 は既に「探索済みリスト」に、2 は既に「探索候補スタック」に存在することから探索候補の対象外となり、4 だけが「探索候補スタック」に積まれます。
while 3 ループ目（終了地点）
- 現在位置：4
- 探索済みリスト：( 1, 5, 4 )
- 探索候補スタック：( 2, 3, 6 )
「探索候補スタック」の一番後ろから 4 が pop され、探索済みリストに格納されます。4 から移動する先の候補は 3 と 5 と 6 ですが、5 は既に「探索済みリスト」に存在することから探索候補の対象外となり、3 と 6 が「探索候補スタック」に積まれます。
while 4 ループ目（終了地点）
- 現在位置：6
- 探索済みリスト：( 1, 5, 4, 6 )
- 探索候補スタック：( 2, 3 )
「探索候補スタック」の一番後ろから 6 が pop され、探索済みリストに格納されます。6 から移動する先の候補は 4 ですが、4 は既に「探索済みリスト」に存在することから探索候補の対象外となり、「探索候補スタック」には何も積まれません。
while 5 ループ目（終了地点）
- 現在位置：3
- 探索済みリスト：( 1, 5, 4, 6, 3 )
- 探索候補スタック：( 2 )
「探索候補スタック」の一番後ろから 3 が pop され、探索済みリストに格納されます。3 から移動する先の候補は 2 と 4 ですが、4 は既に「探索済みリスト」に、2 は既に「探索候補スタック」に存在することから探索候補の対象外となり、「探索候補スタック」には何も積まれません。
while 6 ループ目（終了地点）
- 現在位置：2
- 探索済みリスト：( 1, 5, 4, 6, 3, 2 )
- 探索候補スタック：( )
「探索候補スタック」の一番後ろから 2 が pop され、探索済みリストに格納されます。2 から移動する先の候補は 1 と 3 と 5 ですが、全て「探索済みリスト」に存在することから探索候補の対象外となり、「探索候補スタック」には何も積まれません。
ここで探索候補スタックが空っぽになりますので while ループは終了します。