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

문제: www.acmicpc.net/problem/5014

5014번: 스타트링크

 

 

문제풀이

 

일차원 직선에서의 최단거리를 구하는 문제이다. BFS 알고리즘으로 문제를 풀었다.

 

 

코드

#include <iostream>
#include <queue>

using namespace std;

int dist[1000001];

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

    int f,s,g,u,d;
    cin>>f>>s>>g>>u>>d;

    queue<int> q;
    q.push(s);
    dist[s] = 1;

    while(!q.empty()){
        int cur = q.front();
        q.pop();

        if(cur == g){
            cout<<dist[cur]-1;
            return 0;
        }

        int nu = cur + u;
        if(nu<=f && dist[nu] == 0){
            q.push(nu);
            dist[nu] = dist[cur] + 1;
        }

        int nd = cur - d;
        if(nd>=1  && dist[nd] == 0){
            q.push(nd);
            dist[nd] = dist[cur] + 1;
        }
    }

    cout<<"use the stairs";

    return 0;
}

 

 

결과