CodeIQ 挑戦の記録 : 第78回「今週のアルゴリズム：寝過ごしても大丈夫？」
CodeIQというサイトで問題に挑戦した記録です。
第78回「今週のアルゴリズム：寝過ごしても大丈夫？」
問題文は「正解者発表」ページをご覧下さい。
問題文を要約すると、駅の数と出発駅、降車駅の番号が与えられる。
降車駅を挟んで出発駅側と反対側の駅を折り返して往復する時、一度折り返した駅で
折り返す事はない場合の乗車駅から降車駅までの往復パターンの総数を解答する。
考え方
無向グラフの経路の総数を探索する問題として考える。
グラフ（問題文の例）
- 駅2を出発駅、駅3を降車駅とする
- 降車駅は他の全ての駅と辺がつながっている。
- 出発駅側、向こう側ともに、同じ側には辺はつながっておらず、反対側には全ての駅に辺がつながっている。
この例では7通り。
アルゴリズム
メモ化再帰を用いる。
全ての駅を降車駅の手前側と奥側に分け、再帰関数にて反対側の訪問していない駅全てと降車駅を訪問し、往復する様にトレースし、パターン数を数える。
コードは下記の通り(Ruby)
