[BOJ] #5014 스타트링크

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

5014번: 스타트링크

---

#1697 숨바꼭질과 매우 비슷한, 따로 인접리스트나 그래프를 순회하지 않고 최단거리를 구하는 형태의 문제이다. 거의 똑같은 매커니즘을 공유한다고 보면 되는데, 굳이 다른점이라고는 세부 조건과 출력형식이 다르다는 것...? 이전에 풀었던 문제를 복기하며 한번 더 풀어보았다.

항상 BFS를 이용할때에 명심할 점은, 한번 방문했던 케이스는 visited 배열에 저장되므로 다시 방문할 필요성이 없다는 것 이다. 이 부분을 잘 활용하면 이러한 형식의 문제들을 풀때 아주 유용하게 적용할 수 있다.

#include <iostream>
#include <queue>

#define MAX 1000001

using namespace std;

queue<pair<int,int>> Q;
bool visited[MAX] = { false };

int F,S,G,U,D;

int BFS(int a, int c) {
    visited[a] = true;
    Q.push(make_pair(a,c));

    while (!Q.empty()) {
        int n = Q.front().first;
        int cnt = Q.front().second;
        Q.pop();

        if (n == G) return cnt;

        if (n+U>=1 && n+U<=F && !visited[n+U]) {
            visited[n+U] = true;
            Q.push(make_pair(n+U, cnt+1));
        }
        if (n-D>=1 && n-D<=F && !visited[n-D]) {
            visited[n-D] = true;
            Q.push(make_pair(n-D, cnt+1));
        }
    }

    return -1;
}

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

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

    int total = BFS(S,0);
    total == -1 ? cout << "use the stairs\n" : cout << total << '\n';

    return 0;
}