【Python】2種類のジャンプ幅で目標位置に到達できるか判定し、最小ステップ数を求める方法

数直線上の開始位置 p にいる状態から、左または右へ d1 または d2 単位ずつジャンプできるものとします。このとき、目標位置 q に到達するまでに必要な最小ステップ数を求めるのが、本記事で扱う問題です。

例えば、p = 5、q = 10、d1 = 4、d2 = 3 が入力として与えられた場合、答えは 3 になります。右方向へ4単位のジャンプを2回行って位置13まで進み、そこから左へ3単位ジャンプすれば位置10に到達できるためです。

解法のアプローチ：GCDによる事前チェック＋BFS

この問題は「最大公約数（GCD）」と「幅優先探索（BFS）」を組み合わせることで効率的に解けます。

1. GCDによる到達可能性の判定

d1 と d2 の最大公約数を g とすると、p から何回ジャンプしても到達できる位置は必ず「p + k × g」（kは整数）の形になります。したがって、(p − q) が g で割り切れない場合は、どんなにジャンプを繰り返しても q には到達できません。このケースでは即座に -1 を返して探索を打ち切ることで、無駄な計算を回避できます。

2. BFSによる最小ステップ数の探索

到達可能な場合は、各位置をグラフのノードとみなし、「+d1」「+d2」「−d1」「−d2」の4種類の移動をエッジとしたグラフ上で幅優先探索を実行します。BFSは最短経路を保証するアルゴリズムなので、q に最初に到達した時点のステップ数がそのまま最小値になります。同じ位置を二度以上探索しないよう、visited 集合で訪問済みの位置を管理するのがポイントです。

アルゴリズムの手順

• d1 と d2 の最大公約数 gcd_res を求める
• (p − q) が gcd_res で割り切れない場合は -1 を返す
• 両端キュー（deque）と visited 集合を用意し、ペア (p, 0) をキューに追加して p を訪問済みにする
• キューが空になるまで以下を繰り返す：
  • キューの先頭から要素 (point, step) を取り出す
  • point が q と一致していれば step を返す
  • point + d1、point + d2、point − d1、point − d2 のうち未訪問の位置をすべてキューに追加し、visited に登録する

Python実装例

以下が実際の実装コードです。

from math import gcd
from collections import deque

def solve(p, d1, d2, q):
    gcd_res = gcd(d1, d2)
    if (p - q) % gcd_res != 0:
        return -1
    que = deque()
    visited = set()
    que.appendleft([p, 0])
    visited.add(p)
    while len(que) > 0:
        pair = que.pop()
        point, step = pair[0], pair[1]
        if point == q:
            return step
        if point + d1 not in visited:
            que.appendleft([(point + d1), step + 1])
            visited.add(point + d1)
        if point + d2 not in visited:
            que.appendleft([(point + d2), step + 1])
            visited.add(point + d2)
        if point - d1 not in visited:
            que.appendleft([(point - d1), step + 1])
            visited.add(point - d1)
        if point - d2 not in visited:
            que.appendleft([(point - d2), step + 1])
            visited.add(point - d2)

p = 5
q = 10
d1 = 4
d2 = 3
print(solve(p, d1, d2, q))

入力

p = 5, q = 10, d1 = 4, d2 = 3

出力

3

処理の流れを確認

この入力の場合、探索は次のように進みます。

• ステップ1：5 + 4 = 9、5 + 3 = 8、5 − 4 = 1、5 − 3 = 2 をキューに追加
• ステップ2：各位置からさらに4方向へ展開（例：9 + 4 = 13 など）
• ステップ3：13 − 3 = 10 が q と一致するため、ステップ数 3 を返して終了

計算量の目安

BFSでは各位置を高々1回しか訪問しないため、探索対象となる位置の総数を N とすると、時間計算量は O(N)、空間計算量も O(N) となります。gcd による事前チェックにより、到達不可能なケースではほぼ定数時間で処理を終えられる点も実用的です。

まとめ

2種類のジャンプ幅で目標位置に到達できるかを判定する問題は、「GCDによる割り切り判定」で到達可能性を絞り込み、「BFS」で最短ステップ数を求めるのが定石です。グラフ探索の基本的な考え方を応用できる好例なので、競技プログラミングやアルゴリズム学習の題材としてもおすすめです。