백준 5014 - 스타트링크 - BFS

문제

문제링크 : https://www.acmicpc.net/problem/5014

풀이전략

1. 해당 위치로 도달할 수 있는지 없는지를 찾는 문제이다. 체크배열을 만들어서 중복되는 위치로는 가지 않도록 만들어야한다.
2. 최단거리를 구해야하므로 당연히 BFS이다.
3. Up과 Down일때 범위를 넘지 않도록 주의해야한다.
4. 도달하지 못할 경우 즉 큐가 비었는데도 도착하지 못했을 경우에는 "use the stiars"를 출력한다.

코드

#include<bits/stdc++.h>

using namespace std;

bool ch[1000001];
// F 전체 층, S 지금 위치, G가야할 층 
int F, S, G, U, D;
struct Elve{
    int state, cnt;
    Elve(int a, int b){
        state = a;
        cnt = b;
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> F >> S>> G>> U>>D;
    int res = -1;
    queue<Elve> q;
    q.push(Elve(S,0));
    while(!q.empty()){
        Elve nElve = q.front();
        q.pop();

        if(nElve.state == G){
            res = nElve.cnt;
            break;
        }

        int up = nElve.state + U;
        int down = nElve.state - D;
        if(up <= F){
            if(!ch[up]){
                ch[up] = true;
                q.push(Elve(up,nElve.cnt+1));
            }
        }
        if(down >= 1){
            if(!ch[down]){
                ch[down] = true;
                q.push(Elve(down,nElve.cnt+1));
            }
        }
    }

    if(res == -1) cout << "use the stairs"<<endl;
    else cout << res << endl;

    return 0;
}

소감

체크배열의 존재가 매우 중요했다. 이전에 BFS문제를 많이 풀었기에 이정도 문제는 손쉽게 해결하였다.