Jump Game

오늘 코테 문제를 풀다가 갑자기 머리 속에서 스쳐서 풀어본 문제다.

각 index에 있는 숫자가 내가 점프할 수 있는 max 숫자일때 마지막에 닿을 수 있으면 true 를, 아니면 false 를 리턴 해야한다.

자연스럽게 bfs 탐색이 생각났지만 생각해보니 dfs 탐색도 가능하긴 했다. 이 문제의 최적화는 dp 에 있지만 나는 그냥 bfs 방식으로 풀었다.

생각보다 조건을 넣는게 조금 까다로워서 놀랐지만 그래도 이정도 구현은 잘해서 다행이다.

class Solution {
public:
    bool canJump(vector<int>& nums) {
        vector<bool> visited(nums.size(),false); 
        queue<int> q; 
        q.push(0); 
        visited[0] = true; 

        while(!q.empty()){
            int size = q.size(); 
            for(int i = 0; i < size; i++){
                int first = q.front();
                q.pop(); 

                if(first == nums.size() - 1) return true; 

                int ele = nums[first]; 

                for(int j = 1; j <= ele; j++){
                    if(first + j < nums.size() && !visited[first+j]){
                        //cout << ele << ' ' <<  first + j << ' ' << nums[first+j] << endl; 
                        if(first + j == nums.size() - 1) return true; 
                        if(nums[first + j] != 0){
                            q.push(first + j); 
                            visited[first+j] = true; 
                        }
                    }
                }
            }
        }

        return false; 
    }
};