[leetcode] 45. Jump Game II

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

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 해석

점프 게임을 할 건데 게임 종료 조건은 배열의 맨 끝에 가장 적게 뛰어서 도착하는 것이고 배열에 나와있는 숫자보다 작거나 같게 뛸 수 있다.

 

예를 들어 nums = [2, 3, 1, 4, 4] 라는 배열일 경우

 

출발점은 항상 배열의 0번째 인덱스이다.

따라서 2이기 때문에 1 ~ 2 사이로 뛸 수 있다.

 

그러면 nums[0 + 1] = 3, nums[0 + 2] = 1 로 뛴다.

 

1번째 인덱스로 간 것부터 고려하면 1 ~ 3 사이로 뛸 수 있기 때문에 nums[1 + 1], nums[1 + 2], nums[1 + 3]

2번째 인덱스로 간 것부터 고려하면 1로만 뛸 수 있음으로 nums[2 + 1]

 

현재 nums[2], nums[3], nums[4]에 각각 점프했고 nums[4]에 이미 도착했기 때문에 2가 정답이다.

 

통과 코드

풀이: BFS + Memoization

BFS로만 풀기엔 입력값이 너무 커서 이미 점프했던 인덱스는 고려하지 않도록 Memoization을 사용해서 점프했던 인덱스를 체크했다.

import java.util.*;

class Solution {
    public int jump(int[] nums) {
        Queue<List<Integer>> queue = new LinkedList<>();
        int result = Integer.MAX_VALUE;
        boolean[] memo = new boolean[nums.length + 1];
    
        boolean is_flag = false;

        queue.add(Arrays.asList(0, 0));

        
        if (nums.length == 1) {
            return 0;
        }

        while(!is_flag) {
            List<Integer> arr = queue.poll();

            if(arr == null) {
                break;
            }

            int temp_index = arr.get(0);
            int temp_count = arr.get(1);
            
            for(int i = 1; i <= nums[temp_index]; i++) {
                if (temp_index + i == nums.length - 1) {
                    result = temp_count + 1;
                    is_flag = true;
                    break;
                }
                if (memo[temp_index + i]) {
                    continue;
                }
                queue.add(Arrays.asList(temp_index + i, temp_count + 1));
                memo[temp_index + i] = true;
            }
        }
        return result;
    }
}