Pythonで開始インデックスからリストの末尾に到達できるかをチェックするプログラム

数値のリスト nums と別の数値 k があるとします。インデックス k から開始し、現在いる任意のインデックス i において、ちょうど nums[i] ステップだけ左または右へ移動することができます。このとき、リストの末尾（最後のインデックス）に到達できるかどうかを判定する必要があります。

例えば、入力が nums = [0, 0, 2, 1, 3, 3, 1, 1]、k = 2 の場合、出力は True になります。これは、インデックス 2 から開始してインデックス 4 へジャンプし、その後最後のインデックス 7 に到達できるためです。

解法のアプローチ

この問題は、グラフの探索問題として捉えることができます。各インデックスをノードとみなし、そこから移動可能なインデックスへの辺があるグラフとして扱い、開始地点から末尾へたどり着けるかを確認します。具体的には、次の手順に従います。

• n := nums のサイズ

• visited := サイズ n のリストを作成し、すべて 0 で初期化（訪問済みフラグ）

• tovisit := 初期値として k を含むリスト（探索待ちのスタック）

• tovisit のサイズが 0 より大きい間、以下を繰り返します：

  • i := tovisit の末尾から要素を取り出して削除

  • i が n-1 と等しい場合、True を返す

  • visited[i] が 1 ではない場合：

    • visited[i] := 1 として訪問済みにする

    • up := i + nums[i]（右へのジャンプ先）

    • down := i - nums[i]（左へのジャンプ先）

    • up < n であれば、tovisit の末尾に up を追加

    • down >= 0 であれば、tovisit の末尾に down を追加

• ループが終了しても末尾に到達できなければ、False を返す

この方法では、同じインデックスを二度訪問しないため、無限ループを回避できます。また、スタック（LIFO）を使った深さ優先探索（DFS）として動作します。

実装例

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

class Solution:
   def solve(self, nums, k):
      n = len(nums)
      visited = [0]*n
      tovisit = [k]
      while len(tovisit) > 0:
         i = tovisit.pop()
         if i == n-1:
            return True
         if visited[i] != 1:
            visited[i] = 1
            up = i + nums[i]
            dn = i - nums[i]
            if up < n:
               tovisit.append(up)
            if dn >= 0:
               tovisit.append(dn)
      return False

ob = Solution()
nums = [0, 0, 2, 1, 3, 3, 1, 1]
k = 2
print(ob.solve(nums, k))

入力

[0, 0, 2, 1, 3, 3, 1, 1], 2

出力

True

計算量について

時間計算量は O(n)、空間計算量も O(n) です。各インデックスは最大一度しかスタックに追加されないため、リストのサイズに対して線形の効率で動作します。