[leetcode - 55. Jump Game] java

문제 설명

1. 배열이 주어진다.

2. 최대 거기 적힌 숫자만큼 점프할 수 있다.

3. 목적지에 도달할 수 있는(목적지에 정확히 가거나 그 이상)지 확인하면 된다.

풀이 과정 

1. 간단한 DFS 문제이다.

2. 지금 위치에서 갈 수 있는 모든 곳을 가면서 체크해준다.

3. 그리고 거기서 또 다음 위치로 가서

4. 도달한 곳이 목적지 혹은 그보다 더 갔으면 true이다.

5. (2) 과정에서 이전 경우에 이미 도달했을 수도 있다. 그러면 애는 더이상 체크할 필요가 없다.

코드

class Solution {
    private static boolean check[];
    private static boolean ans;

    public boolean canJump(int[] nums) {
        check = new boolean[nums.length];
        ans = false;
        jump(0, nums);
        return ans;
    }

    private static void jump(int index, int[] nums) {
        check[index] = true;
        int nextIndex = index + nums[index];

        if(nextIndex >= nums.length - 1) {
            ans = true;
            return;
        }

        for(int i=index+1; i<=nextIndex; i++) {
            if(ans) return;
            if(!check[i]) jump(i, nums);
        }
    }
}