스타트링크 (feat. 백준, 5014번)

스타트링크
https://www.acmicpc.net/problem/5014

5014번: 스타트링크

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
int ans[1000001];
bool visit[1000001];
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int F, S, G, U, D;
    cin >> F >> S >> G >> U >> D;
    memset(ans, -1, sizeof(ans[0]) * (F + 1));
    memset(visit, false, F + 1);
    queue<int> q;
    q.push(S);
    ans[S] = 0;
    visit[S] = true;
    while(!q.empty()){
        auto p = q.front(); q.pop();
        if(p + U <= F && !visit[p + U])
            visit[p + U] = true, q.push(p + U), ans[p + U] = ans[p] + 1;
        if(p - D >= 1 && !visit[p - D])
            visit[p - D] = true, q.push(p - D), ans[p - D] = ans[p] + 1;
    }
    if(ans[G] == -1)
        cout << "use the stairs";
    else
        cout << ans[G];
    return 0;
}
// *&)*@*

 

 

1. 강호가 있는 위치(S층)에서 스타트링크가 있는 위치(G층) 으로는 위(U층) 또는 아래(D층) 로만 움직일 수 있습니다.
2. 따라서 S+U와 S-D에 대해서 너비 우선 탐색인 bfs로 모든 탐색을 마쳤을 때, G층의 인덱스에 값이 있다면 그 값을, 없다면 "use the stairs" 를 출력하는 문제입니다.