ITパスポート 2016年 春期 問33

地点XからA・B・Cをすべて経由して地点Yへ行く最短時間【ITパスポート 解説】

正解の理由

解法ステップ

1. 問題を整理する
   • 表は「始点→終点」の時間。
   • Y に直接行けるのは B と C（A→Y は「不可」）。
   • 必ず A・B・C をすべて通る必要がある。
2. 最後に訪れる地点は B か C に限定されることに気づく。
   • なぜなら Y に直接進めるのは B, C のみだから。
3. B または C を最後にする順列（順番）だけ考える。
   • A→B→C（Cが最後）
   • A→C→B（Bが最後）
   • B→A→C（Cが最後）
   • C→A→B（Bが最後）
   • （末尾がAになる順序は直接 Y に行けないため、そのままでは不適）
4. 各順序の合計時間を計算する（始点は X、終点は Y）。
   • X→A→B→C→Y = 20 + 40 + 20 + 60 = 140
   • X→A→C→B→Y = 20 + 30 + 20 + 60 = 130 ← 最短
   • X→B→A→C→Y = 20 + 40 + 30 + 60 = 150
   • X→C→A→B→Y = 40 + 30 + 40 + 60 = 170
5. 最小値を選ぶ：130分（選択肢イ）。

選択肢別の誤答解説

• ア: 110
  • 110分は「X→A（20）→C（30）→Y（60）」の合計110に見えますが、この経路はBを通っていません。問題条件（A,B,Cすべてを経由）を満たしていないため誤りです。
• イ: 130
  • 正解。X→A（20）→C（30）→B（20）→Y（60）で合計130分。Yへ行く直前をBにすることで、すべての地点を経由しつつ最短になります。
• ウ: 140
  • 140分は X→A（20）→B（40）→C（20）→Y（60） の経路です。A→B の順にした場合は合計が大きくなり、イの方が短いです。
• エ: 150
  • 150分は X→B（20）→A（40）→C（30）→Y（60） の順序です。AをBの後に回すと余分に移動時間がかかります。

よくある誤解

1. 「表はどちらが始点か分かりにくい」
   • 表は行が始点、列が終点です。逆に読むと時間を取り違えます。必ず「行→列」の向きで読む習慣をつけてください。
2. 「最後にAでもいいのでは？」と考えるミス
   • AからYへは「不可」となっているため、Aを最後にしたまま直接Yへ行けません。Aを最後にした場合は別の地点を経由してYへ行く必要があり、余分な移動が増えるため最短にはなりにくいです。
3. 「同じ地点を再訪してもよい」ことを見落とす、またはその必要を誤って想定する
   • 再訪は許されますが、追加の移動時間が生じます。最短探索では必要な場合のみ検討します。本問では再訪は無駄になるため考慮しなくてよいです。

補足コラム

• 順列（じゅんれつ）… 順番を並べること。ここではA,B,Cの並べ方を指します。
• ブルートフォース（総当たり）… 可能な組み合わせをすべて試す方法。

FAQ