[BOJ] 폴짝폴짝(1326)

[백준(BOJ)] 폴짝폴짝(1326) C++

문제 : BOJ_1326번 폴짝폴짝

문제 설명

bfs, pair

bfs를 이용한 최소 점프 수를 출력하는 문제입니다.

유사한 문제로는 bfs를 활용한 백준 1697번 숨바꼭질이 있습니다.

---

Solution

dfs와 bfs를 이용하는 문제들 중 어떤 상황에서 두 개 중 하나를 선택해야 되는지 고민이 될 때가 있는데,

목적지에 도달하는 여러 가지 경우의 수를 다 확인해야 되기보다는 목적지에 도달하는 최소 거리, 최소 시간 등의 문제를 풀 때는 보통 bfs로 풀리는 문제들이 많습니다.

---

Description

1. 징검다리에 쓰여 있는 수 들을 각 징검다리의 번호에 맞는 배열에 넣어준다.
   
2. pair를 이용하여 도달한 징검다리의 번호를 pair의 first에, 도달하기까지 점프한 횟수를 pair의 second에 push
   

#include <iostream>
#include <queue>
using namespace std;
queue<pair<int, int>>q;
int st, ed, jump[10001], roof, vis[10001], swc, res; /*swc == switch 원하는 징검다리에
도달하지 못한다면, swc == 0 이 되게하여 -1을 출력하기 위한 변수입니다. */
int main() {
    cin >> roof;
    for (int i = 1; i <= roof; i++) {
        cin >> jump[i]; // 징검다리에 번호에 쓰여있는 수를 넣어줍니다.
    }
    cin >> st;
    cin >> ed;
    q.push(make_pair(st, 0)); // st==시작 징검다리, 0==점프한 횟수
    vis[st] = 1;
    while (!q.empty()) {
        if (q.front().first == ed) {
            res = q.front().second;
            swc++; // q.front().first가 목표한 징검다리에 도달했을 때 swc==1이 됩니다.
            break;
        }
        int now = q.front().first; // now==현재위치
        int cnt = q.front().second; // cnt==count 점프한 횟수
        q.pop();
        for (int i = 1; now + (jump[now] * i) <= roof; i++) {
            int next = now + jump[now] * i;
            if (vis[next] == 0) {
                vis[next] = 1;
                q.push(make_pair(next, cnt + 1));
            }
        }
        for (int i = 1; now - (jump[now] * i) >= 1; i++) {
            int next = now - jump[now] * i;
            if (vis[next] == 0) {
                vis[next] = 1;
                q.push(make_pair(next, cnt + 1));
            }
        }
    }
    if (swc == 0) {
        cout << -1;
    }
    else cout << res; //swc==1이라면 도달하기까지 점프한 횟수를 출력합니다.
}