[백준] 5014번 스타트링크 C++ 코드

코드

#include <iostream>
#include <queue>

using namespace std;

int f,s,g,u,d, visited[1000004],res = -1;
// 적어도 -> 최단거리. 1차원 배열에서의 최단거리
// 가중치가 없으므로 bfs 사용
// 1번도 안움직여도 되는 경우가 있음
// res는 -1로 초기화
int main() {
    // f는 최대 높이, s는 현위치, g는 목표지점, u위 d 아래
    cin >> f >> s >> g >> u >> d;
    queue<int> q;
    q.push(s);
    visited[s] = 1;
    while(q.size()) {
        int pn = q.front();
        if(pn == g) {
            res = visited[pn] - 1;
            break;
        }
        q.pop();
        for(int i : {pn + u, pn - d}) {
            if(i <= 0 || i > f) continue;
            if(!visited[i]) {
                visited[i] = visited[pn] + 1;
                q.push(i);
            }
        }
    }
    if(res == -1) {
        cout << "use the stairs\n";
    } else {
        cout << res << '\n';
    }
    return 0;
}

풀이

적어도 몇 번 눌러야 하는지는 최소 몇 번 눌러야 하는지를 구하는 문제라고 생각했다. 따라서 최단거리를 찾는 문제라고 생각했고, 따라서 1차원 배열에서 최단거리를 찾으면 된다. 가중치는 따로 없으므로 bfs를 사용했다. 한 번도 움직이지 않고 답이 나오는 경우가 있을 수 있으므로 조건문의 res는 -1로 초기화 해주었다.