深さ優先探索

深さ優先探索 †

このページは競技プログラミングに興味のある方向けに深さ優先探索を簡単に説明するページです

深さ優先探索って何？ †

深さ優先探索はDFSとも略記される手法です
木構造のデータを探索する手法なのですが、大雑把にいえば

1.根からスタートし、とりあえず末端までの経路を試してみる
2.その経路(あるいは末端の要素の状態)が条件を満たしていないなら1手前に戻って、そこから別の経路を探してみる
3.1手前に戻った時、その次の手をすでに全部調べ終わっているならさらにもう1手戻る

という形になります

具体的にどんな手法? †

一般に、ゲームの終了状態や組み合わせ問題は各々木構造における末端部分や末端部分への経路に対応付けることが出来ます
つまり、ゲームの終了状態や組み合わせ問題において条件を満たす手順や組み合わせがあるかどうかを木構造における末端部分あるいはそこへ至る経路を探索することで確認することが出来ます
このとき以下の手法をとる探索手法が深さ優先探索です

1.ピポットを一つ用意します。初期位置は木の根とします
2.ピポットが指すノードのフラグをONにします(初期状態ですべてのノードのフラグはOFFとします)
3.ピポットが指すノードがフラグがOFFの子を持つ場合ピポットをそこへ遷移させ、2へ戻ります(必要ならば遷移経路も記録します)
4.ピポットが指すノードが子を持ち、その子のフラグが全てONの場合ピポットを親へと遷移させ3へ戻ります
5.ピポットが指すノードが子を持たないなら、その状態あるいは遷移経路について条件を満たすかどうかを判定します
　 条件を満たしていれば探索を打ち切ります。そうでないならピポットを親へと遷移させ2へ戻ります

フラグのせいで実装がめんどくさいです †

スタックを知っているならもっと簡単に実装できます

スタックとはなんぞや？ †

知らなくても、深さ優先探索を理解することは何とか可能です
(けど、知識レベル的には深さ優先探索の方が上なので、できればスタックを勉強してくださいね)

スタックを勉強しました †

それなら、以下の手法で容易に実装できます

1.根ノードをPUSHする
2.POPする
3.POPしたノードが子ノードをもつならそれらを全てPUSHする。2へ戻る
4.POPしたノードが子ノードを持たないならそのノードへ至る経路あるいはそのノードの状態が条件を満たすかどうかを判定します
　 条件を満たしていれば探索を打ち切ります。そうでないなら2へ戻ります