[LeetCode] 1306. Jump Game III

접근

• 기존 점프 게임처럼 그리디를 쓰는 방법도 있겠지만, DFS 와 백트래킹을 통해 문제를 풀 수도 있음. 
• DFS를 활용할 때에는 Runtime error를 조심하도록 합시다.
• visited 리스트를 활용해 불필요한 재귀를 줄여야 함

 

문제 링크

https://leetcode.com/problems/jump-game-iii/description/

 

솔루션

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        arr_length = len(arr)
        visited = [False for _ in range(arr_length)]

        def dfs(index):
            # if out of bound or already visited
            if index < 0 or index > arr_length-1 or visited[index]:
                return False
            
            if arr[index] == 0:
                return True

            visited[index] = True

            # DFS and if any of return has True, return True
            if dfs(index - arr[index]) or \
                dfs(index + arr[index]):
                return True
            else:
                return False
        
        return dfs(start)