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

백준의 스타트링크(5014) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 한 건물의 전체층수와, 가고자하는 층수, 현재 있는 층수가 주어진다.

- 엘리베이터를 타고 현재 층수에서 가고자하는 층수에 가야하는데, 엘리베이터에 U칸 올라가는 버튼과 D칸 내려오는 버튼

  2개 밖에 없다.

- 이 때, 현재 있는 층수에서 버튼을 몇 번 눌러야지 가고자하는 층수에 도달할 수 있는지 최소의 버튼 수를 출력하면 된다.

[ 문제풀이 ]

1. 가장 기본적인 BFS / DFS 문제이다. 어려울만한 구간이 하나도 없다. 쉽게 생각해보자.

2. 본인은 BFS로 풀이했는데, Queue에 가장 먼저 (현재층수 , 누른 버튼의 횟수) 즉 (S,0)을 넣어주었다.

3. 이후 BFS를 돌리면서, 엘리베이터의 범위 내에서(1 보다 크거나 같고, F(전체층수) 보다 같거나 작으면) 방문하지 않은

   층수였다면, Queue에 push하는 식으로 구현하였다.

[ 소스코드 ]

#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 1000000 + 1
using namespace std;
 
int F, S, G, U, D;
bool Visit[MAX];
 
void Input()
{
    cin >> F >> S >> G >> U >> D;
}
 
int BFS()
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(S, 0));
    Visit[S] = true;
    
    while (Q.empty() == 0)
    {
        int Pos = Q.front().first;
        int Cnt = Q.front().second;
        Q.pop();
 
        if (Pos == G) return Cnt;
 
        if (Pos + U <= F && Visit[Pos+U] == false)
        {
            Q.push(make_pair(Pos + U, Cnt + 1));
            Visit[Pos + U] = true;
        }
        if (Pos - D > 0 && Visit[Pos - D] == false)
        {
            Q.push(make_pair(Pos - D, Cnt + 1));
            Visit[Pos - D] = true;
        }
    }
    return -1;
}
 
void Solution()
{
    int Answer = BFS();
    if (Answer == -1) cout << "use the stairs" << endl;
    else cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}