読者です 読者をやめる 読者になる 読者になる

CodeIQ 挑戦の記録 : 第78回「今週のアルゴリズム:寝過ごしても大丈夫?」

CodeIQ

CodeIQというサイトで問題に挑戦した記録です。

第78回「今週のアルゴリズム:寝過ごしても大丈夫?」

問題文は「正解者発表」ページをご覧下さい。

問題文を要約すると、駅の数と出発駅、降車駅の番号が与えられる。
降車駅を挟んで出発駅側と反対側の駅を折り返して往復する時、一度折り返した駅で
折り返す事はない場合の乗車駅から降車駅までの往復パターンの総数を解答する。

考え方

無向グラフの経路の総数を探索する問題として考える。

グラフ(問題文の例)

f:id:ibeckuu:20160203003241j:plain

  • 駅2を出発駅、駅3を降車駅とする
  • 降車駅は他の全ての駅と辺がつながっている。
  • 出発駅側、向こう側ともに、同じ側には辺はつながっておらず、反対側には全ての駅に辺がつながっている。

f:id:ibeckuu:20160203003552j:plain

f:id:ibeckuu:20160203003607j:plain

この例では7通り。

アルゴリズム

メモ化再帰を用いる。
全ての駅を降車駅の手前側と奥側に分け、再帰関数にて反対側の訪問していない駅全てと降車駅を訪問し、往復する様にトレースし、パターン数を数える。

コードは下記の通り(Ruby)