백준 14248번: 점프 점프 (C++)

https://www.acmicpc.net/problem/14248

14248번: 점프 점프

---

Solved By: BFS

 

#include <iostream>
#include <vector>
#include <queue>
#define MAX 100001
using namespace std;

vector<int> arr(MAX, 0);
int n, s;

int bfs(int node){
    int cnt = 0;
    cnt++;
    queue<int> q;
    q.push(node);
    vector<bool> visited(n + 1, false);
    visited[node] = true;
    //cout << node << '\n';
    
    while(!q.empty()){
        int now = q.front();
        q.pop();
        
        if(now - arr[now] >= 1 && !visited[now - arr[now]]){
            visited[now - arr[now]] = true;
            q.push(now - arr[now]);
            //cout << now - arr[now] << '\n';
            cnt++;
        }
        
        if(now + arr[now] <= n && !visited[now + arr[now]]){
            visited[now + arr[now]] = true;
            q.push(now + arr[now]);
            //cout << now + arr[now] << '\n';
            cnt++;
        }
    }
    return cnt;
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> arr[i];
    cin >> s;
    
    cout << bfs(s);
    return 0;
}