【23日目】深さ優先探索

最近忙しくてあまりできていなかったのだが今日はやります。深さ優先探索(Depth First Search)。正直DFSは何というか単純すぎてあまり好きではないのだが。全4問、順に所感を書いていきます。

24　ALDS_11_B - 深さ優先探索

ALDSの問題は基本アルゴリズムの実装がきちんとできているか確認するのに非常に便利やね。ちなみに問題条件勘違いしてWAくらって若干手間どった。。

25　AOJ 1160 - 島はいくつある？

前Atcoderの方にも似た問題があったような。。典型なのかな。探索した島を消していくことで重複なくできる。

26　AtCoder Beginner Contest 138 D - Ki

(問題の英語名なぜTreeでなくKiなのか。。)与えられた頂点にだけxを加算しておいて、最後に一気にDFSで累積和を出せば解ける。クエリ系ではよくあるパターン。

27　JOI 2009 予選 4 - 薄氷渡り

25番と似ている。違いは探索終了後薄氷を復元しなくてはいけないことくらいかな。

あと、これはDFS全般についてだが、頂点がすでに通ったことがあるかどうかの判定は、再帰関数のforループ内ではなく、再帰呼び出し後の冒頭で行った方が良い気がする(そうしないと24、27のように始点を固定しないパターンに対応しづらい)。

特に問題なかったので次はBFS。これ終わったらやっと単純探索は終わりだーー