僕が考えたこととライフハック

政治経済、ITについて書く。

#4 競プロ 深さ優先探索(DFS)について スタックを用いて Java

今回は深さ優先探索について書いていこうと思います。

深さ優先探索(DFS)とは

木やグラフを探索するアルゴリズムのこと。

イメージとしてはこんな感じ。↓

f:id:rynsk02:20190510160124p:plain

DFS参考画像(ペイントで作った)

「根ノード(root)から出発し、底まで行ったら1つ戻る。戻った先に行ったことがない底があるならそこに行く。それを繰り返す。」

といった感じです。

もっと簡単に言えば、「進めるだけ進んでみる。」ですね。

実際に問題を見てどのように使っているのか見ていきましょう。

解く問題

https://atc001.contest.atcoder.jp/tasks/dfs_a

ATC - 001 - A

リンクに飛ぶと、AtCoderさんが作ったわかりやすい資料があるので見てみると良いかもです。

書いたコード

DFS - ATC001-A

今回は、スタックを用いて実装してみました。スタックは、LIFO(Last In First Out)です。つまり、直近に入れたものを次に取り出すということです。

コードの流れ

(whileループ1週目)スタートから進める方向を探す。進める場所をスタックに入れる。今の場所は行くことができたのでtrueとメモする。

(whileループ2週目)さっき追加された進める場所を取り出し、その場所から進める方向を探す。進める場所をスタックに入れる。今の場所は行くことができたのでtrueとメモする。

(繰り返す)

最後まで行くと追加される要素はなくなるのでWhileループを抜け出す。

goalのメモを見て判定。

まとめ

コメントを見たらなんとなくわかるかなーと思います。

マップの問題であれば、とりあえず行くことができるのかということを調べるには最適なアルゴリズムだと思います。

この考え方はいろんな問題に応用利きそうなので 類題を解きまくりたいとおもいました。