[백준] 1326번 폴짝폴짝

문제: 1326번: 폴짝폴짝

//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <limits>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n; // 징검다리 개수
    cin >> n;

    vector<int> edges(n + 1); // 0번 인덱스 안 써
    vector<int> visits(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> edges[i];
    }
    int a, b; // a번 징검다리에서 시작해서 b번 징검다리로..
    cin >> a >> b;

    int ans = -1;
    queue<pair<int, int>> nexts; // 다리 번호, 점프 횟수
    nexts.push({ a, 0 });
    visits[a] = true;
    while (!nexts.empty()) {
        pair<int, int> cur = nexts.front(); nexts.pop();
        if (cur.first == b) {
            ans = cur.second;
            break;
        }
        // 양의 방향
        for (int i = cur.first + edges[cur.first]; i <= n; i += edges[cur.first]) {
            if (visits[i]) continue;

            nexts.push({ i, cur.second + 1 });
            visits[i] = true;
        }
        // 음의 방향
        for (int i = cur.first - edges[cur.first]; i >= 1; i -= edges[cur.first]) {
            if (visits[i]) continue;

            nexts.push({ i, cur.second + 1 });
            visits[i] = true;
        }
    }
    cout << ans << "\n";

    return 0;
}