5014번 스타트링크 | BFS | 백준 5014 C++ 코드

 

 

이번 포스팅은 백준 5014번 스타트링크입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/5014

5014번: 스타트링크

 

 

 

기본 알고리즘

최단 거리 = BFS (너비 우선 탐색)

 

 

 

전체 코드

 

//백준5014 스타트링크                                                        
 
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int F, S, G, U, D;
const int MAX = 1000001;
int path[MAX];
bool visited[MAX];
vector<int> dx;
queue<int> q;
 
void BFS(int v) {
    visited[v] = true;
    q.push(v);
 
    while (!q.empty()) {
        v = q.front();
        q.pop(); 
        
        for (int i = 0; i < 2; i++) {
            int nv = v + dx[i];
 
            if (0 < nv && nv <= F) {
                if (!visited[nv]) {
                    visited[nv] = true;
                    q.push(nv);
                    path[nv] = path[v] + 1;
                }
            }
        }
        
    }
}
 
int main() {
    cin >> F >> S >> G >> U >> D;
 
    dx.push_back(U);
    dx.push_back(D * -1);
 
    BFS(S);
 
    if (visited[G]) {
        cout << path[G];
    }
    else {
        cout << "use the stairs";
    }
}