LeetCode Jump Game || (JavaScript), bfs/greedy

링크 : https://leetcode.com/problems/jump-game-ii/description/

문제 설명

You are given a 0-indexed array of integers nums of length n. You are initially positioned at index 0.

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at index i, you can jump to any index (i + j) where:

• 0 <= j <= nums[i] and
• i + j < n

Return the minimum number of jumps to reach index n - 1. The test cases are generated such that you can reach index n - 1.

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000
• It's guaranteed that you can reach nums[n - 1].

---

문제 풀이

1. bfs로 접근 (O(n^2)) -> bfs를 돌면서 가장 먼저 발견한 값이 최소가 됨

• queue에 시작 위치, 현재 점프한 횟수를 저장
• 최대 점프 값을 구함 (`nums[currentIndex]`)
• 1번 점프 ~ 최대 점프 구간의 반복문을 돌면서 queue에 유효한 값 추가
  • 다음 위치가 마지막 인덱스일 경우 현재 점프 + 1값 리턴
  • 다음 위치가 nums의 길이보다 작다면 queue에 추가 -> 이것만하면 시간 초과 오류 (특정 위치의 중복 검사가 발생)
    • 앞서 검사했던 자리를 뒤에 다시 검사를 할 필요가 없음 (앞에서 검사한 jump가 더 작은 범위를 가지기 때문에)
    • 이를 제외 시키기위해 `visited`를 활용해 특정 index의 방문여부를 처리

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    if (nums.length === 1) {
        return 0;
    }

    let queue = [[0, 0]];
    let visited = Array.from({length: nums.length}, () => false);
    visited[0] = true;

    while (queue.length > 0) {
        const [currentIndex, currentJumps] = queue.shift();

        const maxJump = nums[currentIndex];

        for (let i = 1; i <= maxJump; i++) {
            const nextIndex = currentIndex + i;

            if (nextIndex === nums.length - 1) {
                return currentJumps + 1;
            }

            if (nextIndex < nums.length && !visited[nextIndex]) {
                visited[nextIndex] = true;
                queue.push([nextIndex, currentJumps + 1]);
            }
        }
    }

    return 0;
};

---

2. greedy로 해결 (O(n))

현재 위치를 기준으로 도달 가능한 범위내에 최대로 점프할 수 있는 위치를 찾는 것이 핵심

변수 선언

• jumpCount = 현재 점프한 횟수
• endPoint = 특정 인덱스에서 도달할 수 있는 범위
• maxRange = 최대로 점프할 수 있는 거리

반복문

• 0부터 마지막 전까지 검사를 진행
• 가능한 범위 (~endPoint까지) 내에서 가장 점프가 큰 값 구하기 (maxRange)
• 가능한 범위의 마지막에 도달했을 때
  • jumpCount 1증가
  • 현재 지정된 구간내에서 가장 멀리 점프가능한 maxRange를 다음 endPoint로 설정
  • endPoint가 nums.length - 1보다 큰 경우는 도달 가능하므로 jumpCount리턴

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    if (nums.length <= 1) {
        return 0;
    }

    let jumpCount = 0;
    let endPoint = 0;
    let maxRange = 0;

    for (let i = 0; i < nums.length - 1; i++) {
        maxRange = Math.max(maxRange, i + nums[i]);

        if (i === endPoint) {
            jumpCount++;

            endPoint = maxRange;

            if (endPoint >= nums.length - 1) {
                return jumpCount;
            }
        }
    }

    return jumpCount;
};

---

결론

bfs는 O(n^2)의 시간 복잡도로 해결, greedy는 O(n)의 시간 복잡도로 해결

greedy가 bfs에 비해 특정 변수를 활용해 규칙성을 띄는 로직을 구현하는 난이도가 좀 더 높은 것 같다.