[백준][5014번] 스타트링크[cpp, c++]

5014번 스타트링크

• 간단한 BFS 문제이다.

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

• 풀이방법
  1) BFS 탐색중 F보다 클 수 없고, 0보다 작을 순 없다.
  2) check2라는 배열을 통해 몇 번째에 찾았는지 검색을 해줬다.

5014번: 스타트링크

 
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
queue<int> q;
bool check[2000000];
int check2[2000000];
int F, S, G, U, D;
vector<int> v;
void bfs() {
    q.push(S);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        if (x == G) { //목표에 갔을 때
            cout << check2[x]-1<< "\n";
            return;
        }
        for (int i = 0; i < 2; i++) {
            int dx = x + v[i];
            if(dx > F || dx < 0) continue;
            if(check[dx] == true) continue;
            q.push(dx);
            check[dx] = true;
            check2[dx] = check2[x]+ 1;
         }
    }
    cout << "use the stairs";
}
 
 
int main(void){
    cin >> F >> S >> G >> U >> D;
    check2[S] = 1;
    check[S] = true;
    v.push_back(U);
    v.push_back(-D);
    bfs();
    return 0;
}