[leetcode #1306] Jump Game III

Problem

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation: 
All possible ways to reach at index 3 with value 0 are: 
index 5 -> index 4 -> index 1 -> index 3 
index 5 -> index 6 -> index 4 -> index 1 -> index 3 

Example 2:

Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true 
Explanation: 
One possible way to reach at index 3 with value 0 is: 
index 0 -> index 4 -> index 1 -> index 3

Example 3:

Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.

Constraints:

・ 1 <= arr.length <= 5 * 10⁴
・ 0 <= arr[i] < arr.length
・ 0 <= start < arr.length

Idea

Backtracking을 이용해 푸는 문제다.

시작점에서 시작해 해당 index의 값만큼 이동할 수 있으며, 계속해서 이동했을 때 값이 0인 index까지 도달하는지 여부를 리턴하면 된다.

해당 index에 도달하지 못 하는 경우는 다음과 같다.

1. index가 array의 범위를 벗어났을 경우
2. 이미 방문했던 index를 다시 방문했을 경우

위 두 가지 조건이 되었을 때 false를 리턴하고, 나머지 경우는 계속해서 0인 index에 도달하는 루트를 찾는다.

2번 조건을 구현하기가 까다로울 수 있다. 하지만 재귀함수를 이용하면 방문 여부를 reset하기 쉽다. 이동할 수 있는 경우를 모두 탐색한 뒤, 방문 여부를 다시 false로 만들면 된다.

canReach 함수에서는 처음에 움직일 수 있는 거리를 구하고, 왼쪽과 오른쪽 index를 인자로 하여 재귀함수를 호출한다.

재귀함수에서는 위 두 가지 조건일 때 false를 리턴하고, 값이 0인 경우 true를 리턴한다. 이 조건에 해당하지 않을 경우 이동 가능한 index를 계산해 탐색을 계속한다. 탐색하기 전에 해당 index의 방문 여부를 true로 설정하고, 왼쪽과 오른쪽 index를 탐색해 결과값을 or로 설정한다. 두 index에 대한 탐색이 끝난 뒤 방문 여부를 다시 false로 설정하고 결과값을 리턴한다.

이렇게 구현하면 0인 index를 만났을 때 반드시 true값이 리턴이 되며, index가 순환될 때 곧바로 false를 리턴하여 반복 탐색하는 것을 차단할 수 있다.

Solution

class Solution {
    int[] arr;
    boolean[] visited;

    public boolean canReach(int[] arr, int start) {
        this.arr = arr;
        this.visited = new boolean[arr.length];

        int distance = arr[start];

        return findReach(start - distance) || findReach(start + distance);
    }

    private boolean findReach(int index) {
        if (index >= arr.length || index < 0) {
            return false;
        }

        if (arr[index] == 0) {
            return true;
        }

        if (visited[index] == true) {
            return false;
        }

        visited[index] = true;
        int distance = arr[index];
        boolean res = findReach(index - distance) || findReach(index + distance);
        visited[index] = false;

        return res;
    }
}

오랜만에 좋은 결과를 얻었다!

Reference

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