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

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

5014번: 스타트링크

4방향이 아닌, 2방향 bfs 문제이다.

우선 dx배열에 up과 down을 저장해주자. (down저장할 때 꼭 마이너스 붙이자ㅜㅜ 그것때문에 조금 당황했다..)

만약 현재 위치와 목표 층수가 같다면 0을 출력하고 종료한다. 그렇지 않다면 bfs 탐색을 시작하자!

​

현재 위치에서 위로 올라가는 경우와, 내려가는 경우에 대해 모두 탐색해주자.

그 경우들이 0층 이상 ~ F층 이하이고, 아직 방문하지 않았다면 큐에 넣어서 다음 탐색을 이어감과 동시에 현재 위치까지 이동하는데 누른 버튼 횟수 + 1을 다음 위치에 저장해주자

그런 다음, 현재 위치와 목표 위치가 같다면 배열에 저장된 값 -1을 출력해주는데, 처음 위치까지의 이동 횟수를 1로 저장했기 때문에 -1을 해주는 것이다! (사실 처음 위치는 이동 횟수가 0인데 1로 저장했으니 -1 해주는 것!)

#include <bits/stdc++.h>

using namespace std;

int f,s,g,u,d;
int visited[1000001];
int dx[2];

void bfs(){
    queue<int> q;
    q.push(s);
    visited[s]=1;

    while(!q.empty()){
        int x = q.front();
        q.pop();

        if(x == g){
            cout << visited[g]-1;
            return;
        }
        for(int i=0; i<2; i++){
            int nx = x + dx[i];

            if(nx > 0 && nx <= f && visited[nx]==0){
                q.push(nx);
                visited[nx] = visited[x] + 1;    
            }
        }
    }
    cout << "use the stairs";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> f >> s >> g >> u >> d;
    dx[0]=u;
    dx[1]=-d;

    if(s == g){
        cout << 0;
    }
    else bfs();
    return 0;
}