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

문제

백준 5014

5014번: 스타트링크

풀이

현재 위치와 이동 횟수를 저장하는 queue를 선언합니다.

위로 올라갈 수 있을 때, 아래로 내려갈 수 있을 때 queue에 push 해주며 bfs를 실행합니다.

현재 위치가 G와 같다면 이동 횟수를 출력합니다.

소스 코드

#include <iostream>
#include <queue>
using namespace std;
bool visited[1000001];
int F, S, G, U, D;
queue <pair<int, int>> q;
void bfs() {
    q.push(make_pair(S, 0));
    while (!q.empty()) {
        // 현재 위치
        int cur = q.front().first;
        // 이동 횟수
        int cnt = q.front().second;
        q.pop();
        // 도착하면 cnt 출력
        if (cur == G) {
            cout << cnt;
            return;
        }
        // 위로 갈 수 있을 때
        if (cur + U <= F) {
            if (!visited[cur + U]) {
                visited[cur + U] = true;
                q.push(make_pair(cur + U, cnt + 1));
            }
        }
        // 아래로 갈 수 있을 때
        if (cur - D >= 1) {
            if (!visited[cur - D]) {
                visited[cur - D] = true;
                q.push(make_pair(cur - D, cnt + 1));
            }
        }
    }
    // q가 비었고 G에 도착하지 못한 경우
    cout << "use the stairs";
    return;
}
int main() {
    cin >> F >> S >> G >> U >> D;
    bfs();
    return 0;
}