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

문제

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

백준 5014

 

문제 내용

건물의 높이는 F층이고, 현재 강호가 있는 곳은 S층이다.

강호는 G층으로 가려하는데, 엘리베이터는 U층 위로 가거나 D층 아래로 가는 버튼뿐이다.

강호가 G층으로 가기 위해 버튼을 몇 번 눌러야 하는지 구하면 된다.

(만약, 버튼을 어떻게 눌러도 G층으로 갈 수 없다면 use the stairs를 출력한다.) 

 

문제 풀이

1차원 int 배열을 선언해 두고, bfs 방식으로 문제를 풀면 된다.

bfs를 통해 방문 체크를 할 때, 버튼을 누른 횟수를 같이 저장한다.

그러면 반복문이 끝나고 visited[G]를 했을 때 결과를 구할 수 있다.

 

코드

#include <iostream>
#include <queue>

using namespace std;
int f, s, g, u, d;
int visited[1000001];

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

    // 전체 f층, s에 있는데, g로 가려함
    // u층 위로 가거나, d층 아래로 감
    cin >> f >> s >> g >> u >> d;

    queue<int> floor;
    floor.push(s);
    visited[s] = 1; // 1에서 시작하기 때문에 출력 시 -1해야 함

    while (!floor.empty()) {
        int cur = floor.front();
        floor.pop();

        if (cur + u <= f && !visited[cur + u]) {
            floor.push(cur + u);
            visited[cur + u] = visited[cur] + 1;
        }
        if (cur - d >= 1 && !visited[cur - d]) {
            floor.push(cur - d);
            visited[cur - d] = visited[cur] + 1;
        }
    }

    if (visited[g] == 0) {
        cout << "use the stairs";
    } else {
        cout << visited[g] - 1;
    }
}