[백준] 스타트 링크 5014번 (c++)

출처 : 5014번: 스타트링크 (acmicpc.net)

5014번: 스타트링크

풀이 방법

경우가 올라가고 내려가는 2경우 밖에 없으므로 bfs를 통해 탐색했다.

bfs의 큐를 통해 방문하지 않은 층이라면 내려가는 경우와 올라가는 경우 두 개의 층을 

범위가 벗어 나지 않으면 큐에 추가해주었다. 

그리고 visited를 활용해 몇번 움직였는지를 저장해 주었다.

#include<bits/stdc++.h>
using namespace std;
// boj num 5014
int F, S, G, U, D;

int visited[1000001];
int bfs() {
    queue<int> q;
    q.push(S);
    visited[S] = 1;
    while(!q.empty()) {
        int floor = q.front();
        q.pop();
        if (floor == G) return visited[floor] - 1;
        if (floor + U <= F) { // 범위 확인
            if (visited[floor + U] == -1) {
                q.push(floor + U);
                visited[floor + U] = visited[floor] + 1; //횟수 저장
            }
        }
        if (floor - D > 0) { //범위 확인
            if (visited[floor - D] == -1) {
                q.push(floor - D);
                visited[floor - D] = visited[floor] + 1; //횟수 저장
            }
        }
    }
    return -1;
}
int main(){
    memset(visited, -1, sizeof(visited));
    cin >> F >> S >> G >> U >> D;
    int ans = bfs();
    if (ans == -1) cout << "use the stairs";
    else cout << ans;
    return 0;
}