最終更新日：2026年7月25日
fe fe-technology algorithm
まず結論
格子状の最短経路の数え方は、右へ進む回数と上へ進む回数の並べ方 として考えます。
基本情報技術者試験では、次のように置き換えると分かりやすいです。
最短経路
= 右と上の並べ方
例えば、目的地までに「右へ2回、上へ2回」進む必要があるなら、
右・右・上・上
の4回の動きを、どの順番で並べるかを数えます。
この場合は、4回のうち上に進む2回の位置を選ぶので、
4C2 = 6通り
です。
直感的な説明
格子状の道で最短経路を考えるときは、遠回りをしません。
左へ戻ったり、下へ戻ったりすると、最短ではなくなるからです。
そのため、使う動きは基本的に次の2種類だけです。
右へ進む
上へ進む
つまり、最短経路を数える問題は、道順を1つずつ数える問題ではなく、
右と上を、どの順番で並べるか
を数える問題です。
例えば、右に2回、上に2回進むなら、次のような道順があります。
右 右 上 上
右 上 右 上
右 上 上 右
上 右 右 上
上 右 上 右
上 上 右 右
これで6通りです。
定義・仕組み
格子状の最短経路では、まず必要な移動回数を数えます。
右に何回進むか
上に何回進むか
次に、合計の移動回数を出します。
全部の移動回数
= 右の回数 + 上の回数
そして、その中から、上に進む場所を選びます。
通り数
= 全部の移動回数 C 上の回数
または、右に進む場所を選んでも同じです。
通り数
= 全部の移動回数 C 右の回数
例えば、右に3回、上に2回なら、全部で5回動きます。
右・右・右・上・上
5回のうち、上に進む2回の位置を選ぶので、
5C2 = 10通り
です。
右に進む3回の位置を選んでも同じなので、
5C3 = 10通り
でも求められます。
このテーマは、基本情報技術者試験の「基礎理論」や「離散数学」と関係する内容です。公式の出題範囲やシラバスは、IPA：基本情報技術者試験 から確認できます。
科目Aでどう出る？
科目Aでは、格子状の図を見て、最短経路が何通りあるかを問う問題として出題されやすいです。
例えば、点Pから点Rを通って点Qへ行く場合を考えます。
点Pから点Rまでが、
右に2回
上に2回
なら、全部で4回動きます。
右・右・上・上
4回のうち、上に進む2回の場所を選ぶので、
4C2 = 6通り
次に、点Rから点Qまでが、
右に3回
上に2回
なら、全部で5回動きます。
右・右・右・上・上
5回のうち、上に進む2回の場所を選ぶので、
5C2 = 10通り
点Rを必ず通るなら、前半と後半を組み合わせます。
P → R：6通り
R → Q：10通り
6 × 10 = 60通り
経由点がある場合は、区間ごとに数えて、最後に掛ける と考えます。
どんな場面で使う？
問題文では、直接「格子の道順」を聞かれなくても、組合せの考え方が必要になることがあります。
例えば、次のような場面です。
決められた回数の処理のうち、
どのタイミングで特定の処理を行うか
これは、格子の最短経路と同じように、
全部の場所の中から、特定の処理を置く場所を選ぶ
と考えられます。
格子問題で身につけたいのは、公式そのものよりも、次の置き換えです。
順番を数える問題
↓
同じものを含む並べ方
↓
組合せで数える
問題文では、処理の並び、状態遷移、探索の考え方を読むときに、この発想が役立ちます。
よくある誤解・混同
格子状の最短経路でよくある誤解は、点の数や線の本数をそのまま組合せに入れてしまうこと です。
| 誤解 | 正しい理解 |
|---|---|
| 点の数を数えて組合せにする | 右に何回、上に何回進むかを数える |
| 4C3 や 5C4 のように、なんとなく近い数で計算する | 全部の移動回数 C 上の回数で考える |
| 経由点があっても全体を一気に数える | 経由点で区切って、それぞれを掛ける |
| 右の回数と上の回数を区別して別々に足す | 並べ方なので組合せで数える |
| 最短経路でも左や下に戻ってよい | 戻ると最短ではなくなる |
今回のように迷ったときは、まず次の2つだけを数えます。
右に何回進むか
上に何回進むか
その後で、
全部の移動回数の中から、
上に進む場所を選ぶ
と考えると、式が自然に決まります。
まとめ（試験直前用）
- 格子状の最短経路は、右と上の並べ方で考える
- 最短経路では、左や下に戻らない
- 全部の移動回数は、右の回数 + 上の回数
- 通り数は、全部の移動回数 C 上の回数で求められる
- 右の回数を選んでも同じ答えになる
- 経由点がある場合は、区間ごとに数えて掛ける
- 点やマスの数ではなく、移動回数を見る