[백준/c++] 5014번: 스타트링크

 

 

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

5014번: 스타트링크

 

 

S층에서 G층에 최소 몇 번 버튼을 눌러야 하는지 출력하면 되는 문제.

S층에서 시작해서 각 노드에 도달할 때까지 걸리는 이동 횟수(버튼 클릭 횟수)를 구하면 되는데, BFS로 풀 수 있다.

visited에 S에서 각 노드에 갈 때 소요되는 이동 횟수를 넣어주면 된다. 이때, 초기 visited 값을 -1로 해서 중복 확인도 해준다.

이동할 수 있는 방법은 u(위로 올라가는 방법)와 d(아래로 내려가는 방법)가 있는데 이 방법으로 이동했을 때 0층 아래로 내려가거나 f층보다 높이 올라가려고 하면 그 방법은 패스하도록 한다. 그리고 방문한 곳이라면 패스해준다. visited는 S에서 해당 층에 가는 이동 횟수 값을 넣는 것이므로 dx 이전 층인 x층까지의 이동 횟수에서 +1을 해준다.

 

 

#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 1000001
using namespace std;

int f, s, g, u, d;
int visited[MAX];

void bfs(){
    queue<int> q;
    q.push(s);
    visited[s] = 0;
    
    while(!q.empty()){
        int x = q.front();
        q.pop();
        
        if(x == g){
            cout << visited[x] << '\n';
            return;
        }
        
        for(int i=0; i<2; i++){
            int dx;
            if(i==0) dx = x + u;
            else     dx = x - d;
            
            if(dx > f || dx <= 0) continue;
            if(visited[dx] >= 0) continue;
            visited[dx] = visited[x] + 1;
            q.push(dx);
        }
    }
    cout << "use the stairs\n";
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> f >> s >> g >> u >> d;
    for(int i=1; i<=f; i++) visited[i] = -1;
    bfs();
    return 0;
}