[Leetcode] 1306. Jump Game III (C++)

문제

1306. Jump Game III

코드

class Solution {
public:
    bool answer = false;
    bool canReach(vector<int>& arr, int start) {
        dfs(arr, start);
        return answer;
    }
    
    void dfs(vector<int>& arr, int cur){
        if (answer or cur < 0 or cur >= arr.size() or arr[cur] < 0) return;
        
        if (arr[cur] == 0) {
            answer = true;
            return;
        }
        
        arr[cur] *= -1;
        dfs(arr, cur+arr[cur]);
        dfs(arr, cur-arr[cur]);
    }
};

접근

한 index에서 움직일 수 있는 위치가 두 개이고 가능한 최소의 경로가 아닌 가능한지에 대한 문제이기 때문에 모든 경우를 살펴보는 것이 좋다고 생각했다. 따라서 재귀로 탐색을 했고 살피려는 인덱스가 배열을 넘어갈 수 있기 때문에 확인해주었고 또한 이미 다른 경로로 확인했는지, 이미 탐색한 위치인지에 대해 확인을 한다. 탐색한 위치는 현재 값을 음수로 바꾸어 놓으므로서 확인하였다.