DFSの勉強メモ
競技プログラミングの勉強会にて、DFS について教えていただいたのでメモ。( Thanks for あのぶるさん( @thatblue_plus! お世話になっております🙏 )
グラフとは
そも、DFS というのは「グラフ」についての用語である。グラフというのは、ノード(点)とエッジ(線)で構成されている、よく見るこういうやつである。時々「木」のことを考えることがあるが、「木」とは「"連結"で"閉路"を持たないグラフ」のことを指す。
DFSとは
深さ優先探索( Depth-First Search )のこと。自分は木のほうがわかりやすいので、まず木で把握する。
DFSは A → B → E → F → J → K → G → C → D → H → L → I の順で探索する。 DFSは「大回りをしてどうなるか」等を見たい時に使い、再帰を利用するのが特徴。
DFSを使って問題を解く
改めて、以前参加して自力ではまったく歯が立たなかった https://atcoder.jp/contests/abc317/tasks/abc317_c がDFSで解けるとのことで、実装をやってみる。
好きな街からスタートして同じ街を二度以上通らずに別の街へ移動するときの、通る道路の長さの和としてありえる最大値を求めてください。
上記の説明より、まさに「大回りをしてどうなるか」を調べるということに該当するので、DFSが適当だと判断できる。再帰利用と「探索済み(seen)」を保持しておくのが肝要な様子、というのを念頭においてコードを書いたが、結果として全然ダメだった。
- TLEになった(リトライ1回目) https://atcoder.jp/contests/abc317/submissions/48960236
- ACでた(リトライ17回目) https://atcoder.jp/contests/abc317/submissions/49134903
ACを出したものも、結局のところ過去にあのぶるさんにペアプロしてもらって書いたコード( https://atcoder.jp/contests/abc317/submissions/46458009 )をほぼ参考にしながら、なんとか書けたという状況となった。結果としてDFSを知っただけではダメだなということを痛感した…。DFSの再帰の中で何をするかというのが肝要。それはそう。
今回の学び
失敗した場合、どのように失敗しているのか、結果をちゃんとみた方がいい。 TLE が出てるということは仕組みはあってて速度の問題かなと思いこんでいたケースがあったが、改めて詳細をみたら「回答が出ない」というバグを抱えていた状態になっていたようだということに後から気づいた。AC7割、TLE3割という感じで、TLEは遅かったのではなく変なループにハマって答えに辿り着かなかったと考えたほうがよさそうだった。仕組みは合ってると思い込んでしまうと永久にTLEから逃れられないので、ちゃんと実行結果の一覧を見にいくようにする。
