CodeIQ: 星間飛行ルートを作ろう！

CodeIQの問題を解いてみた。

お題

■ CodeIQの問題に挑戦しよう！
http://www.hyuki.com/codeiq/#c11

■ 挑戦者求む！【アルゴリズム】星間飛行ルートを作ろう！ by The Essence of Programming 結城 浩│CodeIQ
https://codeiq.jp/ace/yuki_hiroshi/q411

解き方

今回はJavaで実装したんだけど、クラスをいくつか作って解いたこともあって、ソースコードを載せると邪魔ってことで省略。
こんな風にしたってのだけは書いておくことにする。

解き方はそれほど凝ったことはしてなくて、星から次の星のルートを探し、辿っていくという方法。
ルートが200以上になっても終わりが見えなかった星(無限ルート星)があったので、深度を優先した探索はやめて、開始の星を基準星として深度が浅いところを優先的に検索していった。
次の目的地の星が見つかったら今度はその星を基準星に…って感じに見つかるまで探索。

この方法だと無限ルート星にぶつかった時に困るんだけど、もしかしたらその先に目的地があるかもしれないので切り捨てることはせず、20スレッドを作成し、並列で探索させた。
こうしておけば、いくつかのスレッドが無限ルート星で停止していても他のスレッドは探索してくれるだろうということで。

イメージ図

実は、今回問題を解きたかったわけじゃなくて、星空を描きたかっただけだったりする。

まとめ

無事に解けてバッジをいただき、フィードバックにもコメントを載せていただきました。