最終更新日：2026年8月19日
fe fe-technology algorithm
まず結論
格子状の図で最短経路の通り数を求めるときは、必要な「右」と「上」の移動回数を数え、その並べ方を組合せで求めると整理できます。
右に (a) 回、上に (b) 回進む必要があるなら、最短経路数は次の形です。
[ {}_{a+b}C_a ]
また、途中の指定点を必ず通る条件がある場合は、
出発点 → 指定点
指定点 → 到着点
の2区間に分けて、それぞれの最短経路数を求め、最後に掛けます。
一言で覚えるなら、
右と上の回数を数える → nCr → 指定点があれば区間ごとに求めて掛ける。
です。
直感的な説明
例えば、ある地点まで最短で進むために、
右に3回
上に2回
必要だとします。
最短経路なら、余計に左へ戻ったり下へ戻ったりはできません。
したがって、実際に考えるのは5回の移動の順番だけです。
右 右 右 上 上
右 上 右 上 右
上 右 右 右 上
...
5回のうち「上」を置く2か所を決めれば、残り3か所は自動的に「右」になります。
そのため、
[ {}_5C_2 ]
と数えられます。
ここが、格子経路と組合せがつながるポイントです。
定義・仕組み
なぜ組合せで数えられる？
最短経路では、必要な移動回数があらかじめ決まります。
例えば、
右に2回
上に2回
なら、移動は全部で4回です。
右 右 上 上
の4個の並びのうち、どの2か所を「上」にするかを選べば、残りは「右」に決まります。
そのため、
[ {}_4C_2 ]
で求められます。
一般化すると
右に (a) 回、上に (b) 回なら、全移動回数は (a+b) 回です。
そのうち、右の位置を (a) 個選ぶと考えれば、
[ {}_{a+b}C_a ]
です。
上の位置を選んでも同じなので、
[ {}_{a+b}C_b ]
でも同じ値になります。
指定点を必ず通る場合
途中の点Rを必ず通るなら、経路を2つに分けます。
P → R
R → Q
PからRへの行き方が6通り、RからQへの行き方が10通りなら、
P → R の1通り目 × R → Q の10通り
P → R の2通り目 × R → Q の10通り
...
と組み合わせられるので、
[ 6 \times 10 = 60 ]
となります。
「途中を通る」条件では足し算ではなく掛け算になる点が重要です。
このテーマは、基本情報技術者試験の基礎理論やアルゴリズムの考え方と関係します。公式の出題範囲やシラバスは、IPA：基本情報技術者試験から確認できます。
科目Aでどう出る？
科目Aでは、格子状の図を見て最短経路数を求める問題や、途中の指定点を通る条件付き経路数を求める問題として出題されることがあります。
まず移動回数を数える
試験では、いきなり式を作るより、最初に必要な移動を書き出すと安全です。
右に何回？
上に何回？
例えば、
右に4回
上に3回
なら、全部で7回動きます。
したがって、
[ {}_7C_3 ]
または
[ {}_7C_4 ]
です。
指定点があれば分割する
「点Rを通って」などの条件がある場合は、最初から全体を数えないようにします。
P → R を数える
↓
R → Q を数える
↓
最後に掛ける
この判断だけで、かなり解きやすくなります。
判断フロー
格子状の最短経路
↓
必要な右・上の回数を数える
↓
合計移動回数から片方の位置を選ぶ
↓
nCr
↓
途中の指定点あり？
Yes → 区間ごとに求めて掛ける
No → そのまま答え
どんな場面で使う？
格子状の経路数
最も典型的な使い方です。
右にa回
上にb回
→ (a+b)Ca
同じ種類のものを並べる問題
格子経路は、実は「右」と「上」という同じ種類の記号を並べる問題です。
右 右 上 上 上
のような並びを何通り作れるか、と考えられます。
そのため、見た目が経路問題でも、中身は組合せ問題です。
複数段階の選択
指定点を通る経路では、
前半の選び方
×
後半の選び方
という積の法則を使います。
この考え方は、経路問題以外でも「前半と後半を独立に選ぶ」問題で使えます。
よくある誤解・混同
❌ 距離を足せば経路数が求まる
誤りです。
距離と経路の通り数は別です。
距離
→ 何回移動するか
経路数
→ その移動をどう並べるか
❌ 順列 nP r を使う
そのまま順列を使うと、同じ「右」同士や「上」同士まで区別してしまいます。
格子経路では、同じ方向の移動は区別しません。
そのため、位置を選ぶ組合せ nCrで考えるのが分かりやすいです。
❌ 指定点を通るときは2区間の経路数を足す
誤りです。
前半のどの経路にも、後半のどの経路も組み合わせられます。
前半6通り
後半10通り
→ 6 + 10 ではなく 6 × 10
❌ 最短経路なのに左や下へ動く
最短経路では、目的地と反対方向へ戻る動きは不要です。
右上方向にある目的地へ向かうなら、基本的には「右」と「上」だけを数えます。
❌ nCrのrは必ず上の回数にする
右の回数を選んでも、上の回数を選んでも同じです。
[ {}{a+b}C_a = {}{a+b}C_b ]
なので、計算しやすい方を選べます。
まとめ（試験直前用）
- 格子状の最短経路は、移動順の並べ方を数える問題
- 右に (a) 回、上に (b) 回なら ({}_{a+b}C_a)
- 全移動回数の中から、右または上の位置を選ぶと考える
- 最短経路では、余計に戻る移動を入れない
- 指定点を必ず通るなら、前半と後半に分ける
- 指定点を通る経路数は、前半の通り数 × 後半の通り数
- 「経路問題」に見えても、中身は組合せ問題
右・上を数える → nCr → 指定点があれば分けて掛ける。