[5014] 스타트링크

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

빌딩의 높이 F, 스타트링크의 층 G, 현재 층 S, 위로 U층, 아래로 D층이 인풋으로 주어졌을 때

현재 층에서 목표 층 까지 최소 몇 번의 U 또는 D 버튼을 눌러야 하는지를 묻는 문제이다. 

만약 U나 D를 눌렀을 때 갈 수 없는 층이면 가지 않는다. 

Ex) F = 78, S = 50, U = 30 일 때 현재 층에서 U버튼을 누루면 80층이지만 80층은 존재하지 않는 층이기 때문에 가지 못한다.

현재 층에서 위 또는 아래 버튼을 한 번씩 눌러보고 갈 수있으면 큐에 넣어 계속해서 확인해주는 방법으로 풀었다.

즉 거리 값이 모두 1일 경우의 최단거리를 구하는 문제이므로 BFS를 이용했다.

만약 큐가 빌 때 까지 목표층에 도달하지 못한다면 가지 못한다는 뜻이므로 use the stairs를 출력해주면 된다.

버튼 수는 배열을 하나 만들어 큐에 넣을 때마다 현재 층 값에서 1씩 증가하는 방법으로 구했다.

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int f, s, g, u, d;
int cnt[1001000];
queue<int> qu;
int bfs(int pos) {
    cnt[pos] = 1;
    qu.push(pos);
    while (int s = (int)qu.size()) {
        while (s--) {
            int cpos = qu.front();
            qu.pop();
 
            if (cpos == g) return cnt[cpos] - 1;
 
            if (cpos - d > 0 && cnt[cpos - d] == 0) {
                cnt[cpos - d] = cnt[cpos] + 1;
                qu.push(cpos - d);
            }
            if (cpos + u <= f && cnt[cpos + u] == 0) {
                cnt[cpos + u] = cnt[cpos] + 1;
                qu.push(cpos + u);
            }
        }
    }
    return -1;
}
 
int main() {
    scanf("%d %d %d %d %d", &f, &s, &g, &u, &d);
    int res = bfs(s);
    if (res == -1) {
        puts("use the stairs");
    }
    else {
        printf("%d\n", res);
    }
    return 0;
}