leetcode 1306. Jump Game III

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 

 

1. BFS

class Solution {
    public boolean canReach(int[] arr, int start) {
        
        if(start < 0 || arr.length <= start){
        	//배열의 인덱스값이 배열크기를 넘지않도록
            return false;
        }
        if(arr[start] < 0){
        	//arr[start] = -arr[start] 체크, 이미 방문했던 인덱스를 다시 돌면 무한루프를 돌것이기때문
            return false;
        }
        if(arr[start]==0){
        	//정답을 찾았을때, 
            return true;
        }
        arr[start] = -arr[start];//방문했다고 기록을한다.
        int left = start+arr[start];
        int right = start-arr[start];
        boolean la = canReach(arr,left);
        boolean ra = canReach(arr,right);
        return la||ra; 
    }
}

 

2. DFS

class Solution {
    public boolean canReach(int[] arr, int start) {
        
        Queue<Integer> que = new LinkedList<>();
    	int arrLength = arr.length;
    	que.add(start);
    	
    	while(!que.isEmpty()) {
    		//현재 인덱스 위치
    		int idx = que.poll();
    		
    		if(idx < 0 || idx >= arrLength) {
    			//배열의 범위를 넘었을경우
    			continue;
    		}
    		if(arr[idx] < 0) {
    			//만약에 내가 이미 들렸던 위치면
    			continue;
    		}
    		if(arr[idx] == 0) {
    			//0을 찾음
    			return true;
    		}
    		//내가 들렸던 곳을 체크해준다. 만약에 안해주면 큐에 계속 쌓일것이긴 떄문이다.
    		arr[idx] = -arr[idx];
    		
    		if(idx+arr[idx] >= 0) {
    			//왼쪽으로 가는 인덱스
    			que.add(idx+arr[idx]);
    		}
    		if(idx-arr[idx] < arrLength) {
    			//오른쪽으로 가는 인덱스
    			que.add(idx-arr[idx]);
    		}
    	}
    	return false;
    }
}