1306. Jump Game III

[zeikar]

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