백준 5014번 : 스타트링크 (C++)

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

5014번: 스타트링크

 

코드

#include <iostream>
#include <queue>
using namespace std;
int main() {
    int f,s,g,u,d;
    cin>>f>>s>>g>>u>>d; //f최고층 s현재층 g목표층 u업 d다운
    if(s==g)
    {
        cout<<0;
        return 0;
    }
    int arr[f];
    for(int i=1;i<=f;i++)
    {
        arr[i]=-1;
    }
    arr[s]=0;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int cur=q.front(); q.pop();
        if(cur+u<=f && arr[cur+u]==-1)
        {
            arr[cur+u]=arr[cur]+1;
            q.push(cur+u);
        }
        if(cur-d>=1 && arr[cur-d]==-1)
        {
            arr[cur-d]=arr[cur]+1;
            q.push(cur-d);
        }
    }
    if(arr[g]==-1)
    {
        cout<<"use the stairs";
    }
    else
    {
        cout<<arr[g];
    }
    return 0;
}

 

풀이

 먼저 현재 층과 목표 층이 같으면 버튼을 누를 필요가 없으므로 0을 출력하고 끝낸다. 현재 층과 목표 층이 같지 않다면 버튼을 눌러서 갈 수 있는지 아니면 가는 게 불가능한지 검사해야 한다. 1~f 층까지 가는데 버튼을 몇 번 눌렀는지 저장하는 배열을 만들고 방문하지 않은 층을 표시하기 위해 초깃값을 -1로 만들어준다. 17행에서 시작 층의 버튼 누른 횟수를 0으로 만들어주고 BFS를 수행한다. BFS를 수행한 뒤에 배열의 값이 방문하지 않았음을 나타내는 -1이라면 use the stairs를 출력하고 그게 아니라면 버튼을 누른 횟수를 출력한다.