C++で解くジャンプゲームIII：BFSによる到達可能性判定

問題概要

非負整数からなる配列 arr が与えられ、最初は配列の指定された開始インデックスに位置しています。現在インデックス i にいるとき、i + arr[i] または i - arr[i] へジャンプすることができます。このとき、値が 0 であるインデックスに到達可能かどうかを判定してください。ただし、どの時点でも配列の範囲外へジャンプすることはできません。

例えば、入力が arr = [4,2,3,0,3,1,2]、開始位置が 5 の場合、出力は true になります。5 → 4 → 1 → 3 または 5 → 6 → 4 → 1 → 3 という移動経路で、値が 0 のインデックス 3 に到達できるためです。

解法アプローチ：幅優先探索（BFS）

この問題は、グラフの到達可能性判定として捉えることができます。各インデックスをノードとみなし、ジャンプで移動できる先をエッジと考えると、「開始ノードから値 0 のノードに到達できるか」という問題に置き換えられます。これには幅優先探索（BFS）が有効です。

以下の手順で解いていきます。

• n := 配列 arr のサイズ
• キュー q を用意して start を挿入する。さらに、訪問済みインデックスを管理する集合 visited を定義し、start を追加する
• キューが空でない限り、以下を繰り返す：
  • curr := キューの先頭要素を取り出す
  • arr[curr] == 0 であれば true を返す
  • curr + arr[curr] < n かつ curr + arr[curr] が未訪問の場合、キューと visited に追加する
  • curr - arr[curr] >= 0 かつ curr - arr[curr] が未訪問の場合、キューと visited に追加する
• ループが終了しても見つからなければ false を返す（値 0 のインデックスには到達できない）

一度訪れたインデックスを visited で記録しておくことで、同じ場所を何度も探索する無駄を防げます。その結果、計算量は配列サイズに対して O(n) に抑えられます。

C++による実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        int n = arr.size();
        queue<int> q;
        q.push(start);
        set<int> visited;
        visited.insert(start);
        while(!q.empty()){
            int curr = q.front();
            q.pop();
            if(arr[curr] == 0)return true;
            if(curr + arr[curr] < n && !visited.count(curr + arr[curr])){
                q.push(curr + arr[curr]);
                visited.insert(curr + arr[curr]);
            }
            if(curr - arr[curr] >= 0 && !visited.count(curr - arr[curr])){
                q.push(curr - arr[curr]);
                visited.insert(curr - arr[curr]);
            }
        }
        return false;
    }
};
main(){
    vector<int> v = {4,2,3,0,3,1,2};
    Solution ob;
    cout << (ob.canReach(v, 5));
}

入力

[4,2,3,0,3,1,2]
5

出力

1

まとめ

ジャンプゲームIIIは、BFSを用いた典型的な到達可能性判定の問題です。各インデックスからの左右へのジャンプをグラフの辺とみなすことで、キューと訪問済み集合を使ったシンプルな探索で効率的に解けます。計算量・空間計算量ともに O(n) であり、配列サイズに対して線形時間で動作する点が大きな特徴です。