『プログラミングコンテストチャレンジブック [第2版]』において、「すべての基本」とされているのが「全探索」である。全探索アルゴリズムの典型は「深さ優先探索」と「幅優先探索」であり、まずは前者を理解したいと思った。
そのためには、本を読むだけではなく、多くの問題を解く必要があるだろう。「頻出典型アルゴリズムの演習問題としてよさげなやつ」には、深さ優先探索で解けそうな問題が6問挙げられている。
2問目の「Sum of Integers」には、けっこう時間がかかってしまった。再帰関数の終了条件が、Ballとくらべて複雑なのが原因だろう。独力の解答でも間違いではなかったのだが、他の解答例を参考に直してみた。こちらのほうが終了条件がわかりやすい気がする。
実はこれらの2問、以前AIZU ONLINE JUGDEにトライしていたときには解けなかったものだった。できなかったことができるようになるのは楽しい。3問目以降にも挑戦しよう。
3問目の「The Number of Island」、4問目の「Block」、6問目の「Property Distribution」も解けた。
3問目は前掲書籍の例題とほぼ同じ内容。4問目も似た内容だが、RubyのArrayの使い方を理解できておらずハマってしまった。
6問目も似ているが、再帰だとスタックオーバーフローになってしまった。スタックを使う方式で書き換えて、なんとか解けた。
5問目の「Sergeant Rian」は難しそうなのでまた今度。
