Pythonでインデックスkから開始してリストの末尾に到達できるか判定するプログラム

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

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

解決のためのアプローチ

この問題は、到達可能なインデックスを順番に辿っていくことで解決できます。具体的には、深さ優先探索（DFS）の考え方を用い、スタックを使って次に訪問すべきインデックスを管理します。すでに訪問したインデックスは記録しておき、無限ループを防ぎます。

手順は以下の通りです。

• n := nums のサイズとする
• visited := サイズnのリストを作成し、すべて0で初期化する
• tovisit := 要素として k を含むリストを作成する
• tovisit が空でない限り、以下を繰り返す
  • i := tovisit の末尾から要素を取り出す（pop）
  • i が n-1 と等しければ、True を返す
• visited[i] が 1 でない場合、以下を実行する
  • visited[i] := 1 とする
  • up := i + nums[i]
  • down := i − nums[i]
  • up < n であれば、up を tovisit の末尾に追加する
  • down ≥ 0 であれば、down を tovisit の末尾に追加する
• すべての探索が終わっても末尾に到達できなければ、False を返す

それでは、理解を深めるために実際の実装を見てみましょう。

実装例

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) となります。ここで n はリストの長さです。