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

5014번: 스타트링크

bfs를 응용한 문제이다. S에서 G에 도달할 때 버튼 수를 찾으면 되는데 이 때 버튼은 U, D로 각각 위로 몇 층, 아래로 몇 층을 가는지 알려준다. 즉 D가 0이면 아래 층으로 갈 수 없다는 뜻이다. 먼저 S와 G를 입력받을 때 두 수가 같다면, 같은 층에 위치한 것으로 0을 출력하면 된다. 아니면 bfs를 돌게 되는데 이미 지나간 곳은 check 배열로 확인을 해준다. count의 경우 먼저 도착한 경우가 가장 작은 수이기 때문에 check로 확인을 해줘도 가장 작은 값을 가지게 된다. 만약 count가 F보다 커지는 경우 최악의 수를 넘긴 것이므로 도달할 수 없다고 판단하고 use the stairs를 출력한다.
bfs로 구현한다고 생각해내기만 하면 금방 해결할 수 있는 문제이다. 괜히 dp를 생각하다가 시간이 오래 결렸다.

#include <iostream>
#include <queue>

using namespace std;

int F, S, G, U, D, res = 0;
bool check[1000001];

void bfs() {
    queue<pair<int, int>> q;

    q.push({ S,0 });
    check[S] = true;

    while (!q.empty()) {
        int cur = q.front().first;
        int count = q.front().second;

        q.pop();

        if (cur == G) {
            res = count;
            break;
        }
        if (count > F) {
            break;
        }

        int next;

        next = cur + U;
        if (next >= 1 && next <= F && !check[next]) {
            q.push({ next,count + 1 });
            check[next] = true;
        }

        next = cur - D;
        if (next >= 1 && next <= F && !check[next]) {
            q.push({ next,count + 1 });
            check[next] = true;
        }
    }
}

void solution() {
    bfs();

    if (res == 0) cout << "use the stairs";
    else cout << res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> F >> S >> G >> U >> D;

    if (S == G) {
        cout << 0;
    }
    else solution();

    return 0;
}