[C++]백준 5014번 스타트링크

📌문제 링크

---

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

📌문제 설명

---

bfs로 간단하게 해결 가능합니다. 각 층에서 U층, D층 만큼 이동 가능할 때의 값을 계속 저장한 후 G에 도착했을때 값을 출력하면 됩니다.

📌코드

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
int F, S, G, U, D, tower[1000001];
using namespace std;

void input(){
    cin >> F >> S >> G >> U >> D;
}

void bfs(){
    for(int i = 0; i <= F; i++){
        tower[i] = -1;
    }
    queue<pair<int, int>> q;
    q.push({S, 0});
    tower[S] = 0;
    while(!q.empty()){
        auto [idx, cnt] = q.front();
        q.pop();
        if(idx == G){
            cout << cnt;
            exit(0);
        }
        if(idx + U <= F && U != 0){
            if(tower[idx + U] == -1){
                tower[idx + U] = cnt + 1;
                q.push({idx + U, cnt + 1});
            }
        }
        if(idx - D >= 1 && D != 0){
            if(tower[idx - D] == -1){
                tower[idx - D] = cnt + 1;
                q.push({idx - D, cnt + 1});
            }
        }
    }
    cout << "use the stairs\n";
}

void solve(){
    input();
    bfs();
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}