C++でJump Game IVを解く：BFSによる最小ジャンプ回数の求め方

問題の概要

整数型の配列 arr が与えられ、最初はインデックス 0 にいるものとします。1ステップごとに、次のいずれかの方法でジャンプが可能です。

• インデックス i から i + x へ移動（条件：i + x < n）
• インデックス i から i - x へ移動（条件：i - x >= 0）
• arr[i] と arr[j] が同じ値で、i と j が異なる場合、i から j へ移動

ここで n は配列のサイズです。この問題の目的は、配列の最後のインデックスに到達するために必要な最小ジャンプ回数を求めることです。

入力例と出力

たとえば、入力が次のとおりだったとします。

{20,-5,-5,25,20,5,5,5,1,25}

この場合、出力は 3 になります。インデックス 0 → 4 → 3 → 9 という3回のジャンプで、最後のインデックスに到達できるからです。

解法の考え方：幅優先探索（BFS）

この問題は、グラフの最短経路問題として捉えることができます。各インデックスをノード、ジャンプ可能な移動をエッジとみなせば、開始地点（インデックス 0）から終点（インデックス n-1）までの最短距離を求める問題になります。最短距離を求めるには、幅優先探索（BFS）が最適です。

アルゴリズムの手順は以下のとおりです。

1. 値をキー、その値が出現するインデックスのリストを値とするマップ m を定義します。
2. n を配列 arr のサイズとします。
3. i を 0 から n - 1 までループし、m[arr[i]] の末尾に i を追加していきます。
4. 訪問済みを管理するセット visited に 0 を追加します。
5. キュー q を定義し、0 をプッシュします。
6. レベル（lvl）ごとにBFSを実行します。
   • sz をキューの現在のサイズとします。
   • sz が 0 になるまで次を繰り返します。
     • curr にキューの先頭要素を取り出して格納します。
     • curr が n - 1 と等しければ、lvl を返します（最短ジャンプ回数が確定）。
     • i - 1 が 0 以上で未訪問なら、i - 1 をキューに追加し、visited に登録します。
     • i + 1 が n 未満で未訪問なら、i + 1 をキューに追加し、visited に登録します。
     • m[arr[curr]] に含まれる各インデックス j について、未訪問ならキューに追加し、visited に登録します。
     • 処理が終わったら、m から arr[curr] を削除します。これにより、同じ値を持つインデックスへのジャンプ候補を二度と調べずに済み、計算量を大幅に削減できます。
7. キューが空になってもゴールに到達できない場合は、-1 を返します。

C++による実装例

以下は、上記のアルゴリズムをC++で実装した例です。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int minJumps(vector<int>& arr) {
        map<int, vector<int> > m;
        int n = arr.size();
        for (int i = 0; i < n; i++) {
            m[arr[i]].push_back(i);
        }
        set<int> visited;
        visited.insert(0);
        queue<int> q;
        q.push(0);
        for (int lvl = 0; !q.empty(); lvl++) {
            int sz = q.size();
            while (sz--) {
                int curr = q.front();
                q.pop();
                if (curr == n - 1)
                return lvl;
                int i = curr;
                if (i - 1 >= 0 && !visited.count(i - 1)) {
                    q.push(i - 1);
                    visited.insert(i - 1);
                }
                if (i + 1 < n && !visited.count(i + 1)) {
                    q.push(i + 1);
                    visited.insert(i + 1);
                }
                for (int j = 0; j < m[arr[curr]].size(); j++) {
                    if (!visited.count(m[arr[curr]][j])) {
                        q.push(m[arr[curr]][j]);
                        visited.insert(m[arr[curr]][j]);
                    }
                }
                if (m.count(arr[curr])) {
                    m.erase(arr[curr]);
                }
            }
        }
        return -1;
    }
};
main(){
    Solution ob;
    vector<int> v = {20,-5,-5,25,20,5,5,5,1,25};
    cout << (ob.minJumps(v));
}

入力

{20,-5,-5,25,20,5,5,5,1,25}

出力

3

まとめ

Jump Game IVは、BFSを応用することで効率的に解ける典型的な最短経路問題です。ポイントは、同じ値を持つインデックスへのジャンプを「エッジ」として扱うこと、そして一度処理した値をマップから削除して重複探索を防ぐことの2つです。これにより、配列のサイズを n とすると、計算量は O(n log n) 程度に抑えられます（マップ操作の log 係数を含む）。同様の問題に取り組む際は、状態をグラフとしてモデル化し、BFSでレベルごとに探索する発想が非常に役立ちます。