[Baekjoon,5014]스타트링크

해결

현재 층과 목표 위치까지의 최단 거리로 도달할 수 있는 방법을 찾으면 된다. 그렇기 때문에 BFS를 이용하면 된다. 너비 우선 탐색 시 큐에 현재 층과 몇 번 버튼을 눌렀는 지 같이 저장하며 탐색을 한다. 이를 이용하여 각 정점을 탐색하다 목표하는 위치가 나왔을 때 버튼을 누른 회수를 반환하면 된다. 탐색 시 현재 위치에서 아래 두 가지를 택하여 이동한다.

• 위로 이동
• 아래로 이동

이때 다음 정점이 범위에 벗어나는 경우 그 정점을 탐색하면 안된다.

구현

구현 시 주의할 점은 0층은 존재하지 않기 때문에 1층부터 시작한다는 것이다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int top,up,down;

inline bool inRange(int pos)
{
    return 1<=pos && pos<=top;
}

// 너비 우선 탐색으로 최단 거리를 찾는다.
int bfs(const int start, const int goal)
{
    vector<bool> discovered(top+1);
    // <현재 위치, 버튼을 누른 회수>
    queue<pair<int,int> > q;
    discovered[start]=true;
    q.push(make_pair(start,0));
    int ret;
    while(!q.empty())
    {
        int here=q.front().first;
        int count=q.front().second;
        q.pop();
        // 목표에 도착한 경우 
        if(here==goal)
            return count;
        
        // 위쪽 아래쪽 모두 시도한다.
        int nextUp=here+up;
        int nextDown=here-down;
        if(inRange(nextUp) && !discovered[nextUp]) 
        {
            discovered[nextUp]=true;
            q.push(make_pair(nextUp,count+1));
        }
        if(inRange(nextDown) && !discovered[nextDown])
        {
            discovered[nextDown]=true;
            q.push(make_pair(nextDown,count+1));
        }
    }
    // 엘리베이터로 갈 수 없는 경우
    return -1;
}

int main()
{
    int start,goal;
    cin>>top>>start>>goal>>up>>down;
    
    int ret=bfs(start,goal);
    if(ret!=-1)
        cout<<ret;
    else
        cout<<"use the stairs";

    return 0;
}