[리트코드] 1306. Jump Game III / Javascript

문제주소 :https://leetcode.com/problems/jump-game-iii/

Jump Game III - LeetCode

---

<문제 설명>

1306. Jump Game III

Medium

165342Add to ListShare

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 * 104
• 0 <= arr[i] < arr.length
• 0 <= start < arr.length

 

<풀이법>

▒ 한줄 개념: 완전탐색 ▒ 

완전탐색을 활용해 푸는 문제입니다. 저는 BFS를 활용하여 풀었습니다.

배열의 모든 인덱스를 방문하면서, 해당 값이 0일 경우 true를 반환하는 것이 주요 개념입니다. 

 

자세한 풀이과정은 다음과 같습니다.

1. visited[] 배열 false로 초기화

2. queue에 시작 위치 삽입

3. queue에 원소가 존재할 동안 반복(bfs)

  3-1. queue의 가장 앞 원소 pop -> idx값

  3-2. pop한 idx값의 value값을 얻어옴

  3-3. value = 0 일 경우, return true;

  3-4. idx와 value 값을 활용해 좌/우 모두 확인하여, 점프 가능한 위치를 큐에 삽입

 

 

 

<코드(Javascript)>

/**
 * @param {number[]} arr
 * @param {number} start
 * @return {boolean}
 */
var canReach = function(arr, start) {
    const visited = [];
    arr.map(_ => {
        visited.push(false);
    });
    
    const queue = [start];
    visited[start] = true;
    while(queue.length){
        const idx = queue.pop();
        const val = arr[idx];
        if(val === 0){
            return true;
        }
        if(idx - val >= 0 && !visited[idx - val]){
            queue.push(idx - val);
            visited[idx - val] = true;
        }
        if(idx + val < arr.length && !visited[idx + val]){
            queue.push(idx + val)
            visited[idx + val] = true;
        }
    }
    
    return false;
};

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest