Pythonで解く!虫が家にたどり着くための最小ジャンプ回数を求めるアルゴリズム

問題概要

「forbidden」という配列が与えられます。forbidden[i] は、虫(バグ)がその位置 forbidden[i] へジャンプしてはいけないことを示します。さらに、a、b、x という3つの値も与えられます。虫の家は数直線上の位置 x にあり、虫は初期状態で位置 0 にいます。虫は以下のルールに従ってジャンプできます。

• 正確に a だけ前(右)方向へジャンプできる
• 正確に b だけ後ろ(左)方向へジャンプできる
• 後ろ向きのジャンプを2回連続で行うことはできない
• 配列 forbidden に含まれる位置にはジャンプできない
• 家より先へ前方向にジャンプすることは可能だが、負の位置にはジャンプできない

目標は、虫が家(位置 x)にたどり着くために必要な最小ジャンプ回数を求めることです。どのような順序でも到達できない場合は -1 を返します。

入力例と動作の流れ

たとえば、forbidden = [2, 3, 7, 9, 12]、a = 4、b = 2、x = 16 が与えられた場合、出力は 7 になります。

位置 0 から出発し、a = 4 ずつ前へ2回ジャンプして 4、8 に到達します。しかし次の 12 は禁止位置のためジャンプできません。そこで b = 2 後ろへ下がって 6 に移動し、続けて 10、14、18 と前へ進み、最後に2回後ろへ下がって 16(家)に到達します。合計 7 ステップです。

解法のアプローチ:BFS(幅優先探索)

この問題は最短経路問題として捉えることができ、幅優先探索(BFS)を使うことで効率よく解けます。各状態は「現在位置」「ジャンプ回数」「直前のジャンプが後ろ向きかどうか」の3つの情報で管理します。

アルゴリズムの手順

1. キューにタプル (x, 0, True) を入れ、forbidden リストをセットに変換します。
2. 探索範囲の上限 lim を「a + b + max(x, forbidden の最大値)」として計算します。これにより、必要以上に遠くを探索する無駄を防げます。
3. キューが空になるまで、以下を繰り返します。
   • (curr, jumps, is_b) をキューから取り出します。
   • curr が forbidden に含まれる場合、または 0 ≤ curr ≤ lim を満たさない場合はスキップします。
   • curr を forbidden に追加して訪問済みにします(同じ位置を再探索しないため)。
   • curr が 0 であれば jumps を返します。
   • is_b が True の場合のみ (curr + b, jumps + 1, False) をキューに追加します(後ろ向きジャンプの連続を防止)。
   • (curr - a, jumps + 1, True) をキューに追加します。
4. キューが空になったら到達不可能なので -1 を返します。

ポイント: この実装では、家(位置 x)から出発して 0 へ向かう「逆方向の探索」を行っています。前方向の a ジャンプと後ろ方向の b ジャンプを入れ替えても問題の構造は対称であるため、同じ結果が得られます。

Python 実装例

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

def solve(forbidden, a, b, x):
    queue, forbidden = [(x, 0, True)], set(forbidden)
    lim = max(max(forbidden), x) + a + b
    while queue:
        curr, jumps, is_b = queue.pop(0)
        if curr in forbidden or not 0 <= curr <= lim:
            continue
        forbidden.add(curr)
        if curr == 0:
            return jumps
        if is_b:
            queue.append((curr + b, jumps + 1, False))
        queue.append((curr - a, jumps + 1, True))
    return -1

forbidden = [2, 3, 7, 9, 12]
a = 4
b = 2
x = 16
print(solve(forbidden, a, b, x))

入力

[2, 3, 7, 9, 12], 4, 2, 16

出力

7

まとめ

禁止位置の回避、後ろ向きジャンプの連続制限、負の位置への移動禁止といった複数の制約があるため、単純な貪欲法では最適解を保証できません。BFS で「位置」と「直前の移動方向」を状態として管理しながら探索することで、最小ジャンプ回数を確実に求められます。探索範囲を lim で打ち切ることで、計算量は状態数に比例する O(lim) 程度に抑えられます。