Problem link
https://leetcode.com/problems/jump-game-iii/
Problem Summary
배열의 인덱스 i에서 i + arr[i], i - arr[i]로 점프를 할 수 있을 때 0인 곳으로 갈 수 있는지 출력하는 문제.
Solution
DFS / BFS로 돌려주면 되는데 BFS로 돌렸다.
Source Code
from typing import List
class Solution:
def canReach(self, arr: List[int], start: int) -> bool:
queue = [start]
visited = [False] * len(arr)
visited[start] = True
ans = False
while queue:
idx = queue.pop(0)
if arr[idx] == 0:
ans = True
break
left = idx - arr[idx]
if left >= 0 and not visited[left]:
queue.append(left)
visited[left] = True
right = idx + arr[idx]
if right < len(arr) and not visited[right]:
queue.append(right)
visited[right] = True
return ans