[5014번] 스타트링크

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

5014번: 스타트링크

건물 층을 엘리베이터로 방문하는데 목적층에 도달하기 위해 엘리베이터 버튼을 적어도 몇 번 눌러야 하는지 구하는 문제입니다.

적어도라는 말은 최소로 버튼을 눌러보는 것으로 바꿔서 생각할 수 있습니다.

최소로 버튼을 눌러서 각 층을 방문한다고 생각할 수 있는데 각 층을 정점이라고 생각해 보면, BFS로 문제를 해결하면 되겠습니다.

 

각 층에 방문할 때 dist 배열에는 최소로 버튼을 누르는 횟수를 저장하면서, 동시에 해당 층을 방문했었는지도 알 수 있도록 할 것인데요. 

점화식은 dist[i] : i번 층에 방문할 때 최소로 버튼을 누르는 횟수입니다.

 

단 dist 배열의 초기값을 -1로 해주었는데, 초기값을 0으로 할 수 없는 이유는 코드 라인 12에서 처음 시작하는 층의 버튼을 누른 횟수는 0이라고 저장을 하여 0이 의미 있는 값이 되었기 때문입니다.

따라서 dist 배열에 -1이 들어있다는 것은 아직 해당 정점(층)을 방문하지 않았다는 의미를 갖고 있습니다.

정답은 dist[g]에 들어있으며, 이 값이 -1이라면 아무리 버튼을 눌러도 갈 수 없는 층입니다. 

 

[코드]

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int dist[1000001];
int main() {
    int f, s, g, u, d; //총 층수, 현재층, 목적층, 증가 층수, 감소 층수
    cin >> f >> s >> g >> u >> d;
    memset(dist, -1, sizeof(dist));
    queue<int> q;
    q.push(s);
    dist[s] = 0;
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        if (now + u <= f) { //up버튼을 눌렀을 때
            if (dist[now + u] == -1) {
                q.push(now + u);
                dist[now + u] = dist[now] + 1;
            }
        }
        if (now - d >= 1) { //down 버튼을 눌렀을 때
            if (dist[now - d] == -1) {
                q.push(now - d);
                dist[now - d] = dist[now] + 1;
            }
        }
    }
    if (dist[g] == -1) {
        cout << "use the stairs" << '\n';
    } else {
        cout << dist[g] << '\n';
    }
    return 0;
}

[결과]

10 1 10 2 1 //input
6 //output
100 2 1 1 0 //input
use the stairs //output