[BFS]백준 5014번 스타트링크

백준 5014번

스타트링크

알고리즘을 분류 별로 풀면서 항상 궁금한 것은 어떤 문제가 주어졌을 때 어떤 알고리즘이 가장 적합할지는 어떻게 찾는지였다.

이 문제는 BFS 라는 문제 분류가 없으면 한참을 고민하거나 단순 반복문으로 해결하려고 했을 것 같다.

하지만 시간 복잡도 등을 고려했을 때 큐를 사용한 BFS 방식이 가장 효율적인 것 같다.

처음 시작하는 층 S 는 가장 처음 큐에 push 된다.

해당 층에서부터 갈 수 있는 충 두 개 (위 버튼을 눌렀을 때, 아래 버튼을 눌렀을 때)를 뽑고, 해당 층이 유효한 층인지 확인한다. (꼭대기 층보다 높지 않은지, 0층보다 높은지)

만약 유효하다면 큐에 넣고, 방문 여부를 기록한다.

유효하지 않다면 그냥 넘어간다.

이런 식으로 반복하면, 더 이상 담을 층이 없어서 queue가 empty인 경우에는 엘레베이터를 이용해 갈 수 없는 경우가 된다.

만약 목표층을 찾게 되면 해당 층에 오기 까지 버튼을 몇 번 눌렀는지 출력한다.

층을 관리하는 방법이 조금 머리가 아파서 구조체를 사용하거나 배열을 따로 이용할까 했는데, Pair를 이용하니 금새 해결되었다. Pair <층, 버튼을 누른 횟수 > 로 설정하고, queue에 들어갈 때 자신을 호출한 층의 버튼을 누른 횟수 + 1로 저장을 하면 된다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main(){
    int total, start, goal, up, down;
    cin >> total >> start >> goal >> up >> down;
    
    queue<pair<int,int> > q;
    q.push(make_pair(start,0));
    bool visit[1000001]={false,};
    visit[start] = true;
    while(!q.empty()){
        pair<int,int> current = q.front();
        if(current.first == goal){
            cout << current.second;
            return 0;
        }
        q.pop();
        int above = current.first + up;
        int below = current.first - down;
        if(above <= total && !visit[above]){
            q.push(make_pair(above,current.second+1));
            visit[above] = true;
        }
        if(below > 0 && !visit[below]){
            q.push(make_pair(below,current.second+1));
            visit[below] = true;
        }
    }
    cout << "use the stairs\n";
}