💭

アルゴリズム #2 深さ優先探索[python][AtCoder]

1 min read

本記事について

競技プログラミングで使用するアルゴリズムをまとめます。シリーズ第二弾です。
今回は深さ優先探索(DFS)についてまとめます。
誤り等ありましたら、ご指摘いただけたら幸いです。

深さ優先探索(DFS)とは

DFSとは、「depth first search」の略です。
迷路で例えると、「『一定の法則で進み、突き当たったら一つ前の場所まで戻る』を繰り返しゴールを目指す」というイメージです。

実装方法については、stackを用いる方法と再帰関数を用いる方法の2通りあるみたいです。

当アルゴリズムが活用できる問題

本記事で取り扱ったアルゴリズムを活用できる問題を以下にまとめます。
問題、及び回答例を随時追加・更新していく予定です。
回答例はpythonです。

No. 問題(リンク) 回答例(リンク)
1 AtCoder 196_D :Hanjo 回答例 コード

バックナンバー