(C++) - 백준(BOJ) 5014번 : 스타트링크

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

5014번: 스타트링크

bfs로 푼 문제였습니다. 비슷한 문제로는 숨바꼭질 문제가 있습니다.

 

풀이방법

 입력받은 후 bfs를 수행합니다. 올라갈 수 있다면 queue에 다음 층을 방문하고 누른 버튼 수를 함께 queue에 pair형태로 push해줍니다. 내려갈 수 있다면 마찬가지고 push해줍니다.

 

*pop이후에 방문하게 된다면 한 줄만에 방문해서 더 깔끔해 보이지만 시간초과가 납니다. x+u와 x-d가 다음 경로에서 엇갈리면서 중복된 원소를 삽입하게 되기 때문에 미연에 방지하기 위해 push전에 미리 방문해주는 것이 시간초과를 피하는 길입니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int f,s,g,u,d;
int ck[1000001];
int bfs(){
    queue <pii> q;
    q.push({s,0});
    while(!q.empty()){
        int x = q.front().first;
        int cnt = q.front().second;
        q.pop();
        if(x == g) return cnt;
        if(!ck[x+u] && x + u <= f){
            ck[x + u] = 1, q.push({x + u, cnt+1});
        }
        if(!ck[x - d] && x - d >= 1){
            ck[x - d] = 1, q.push({x - d, cnt+1});
        }
    }
    return -1;
}

int main(){
    cin >> f >> s >> g >> u >> d;
    int ans = bfs();
    if(ans == -1) cout << "use the stairs";
    else cout << ans;
}