오늘 코테 문제를 풀다가 갑자기 머리 속에서 스쳐서 풀어본 문제다.
각 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;
}
};