[백준] 5014_스타트링크_BFS (c++) 실1

이전에 푼 촌수세기랑 비슷하게 풀었어요

 

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

 

이 건물은 총 F층이고

나는 지금 S층에 있고, G층으로 가고 싶습니다

버튼이 좀 이상해서 위 버튼을 누르면 +U층으로, 아래 버튼을 누르면 -D층으로 이동합니다

만약 위 아래 버튼을 눌러서 나오는 층이 최저층이나 최고층을 초과하면 이동하지 않습니다

 

최소 버튼 횟수로 원하는 층에 도달하고자 합니다.

 

현재 층을 queue에 넣습니다.

 

n+1 길이의 visited 배열은 -1로 초기화합니다(미방문 의미)

 

S층부터 시작하니까, visited[s]는 0으로 만듭니다.

 

while q가 빌 때까지 돌리면서

만약 현재 원소가 g랑 같으면 멈추고

그 외에는 위로 가는 경우, 아래로 가는 경우를 탐색합니다

해당 층이 미방문인지, 그리고 최저/최고층을 초과하지는 않는지 확인한 후,

해당 층에 현재층+1(버튼 누른 수)를 더해주고, q에 원소로 해당 층을 추가해 줍니다

 

while문이 끝나도 return이 없었으면 불가능하니까 계단 쓰라는 말을 반환해줍시다

 

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main(){
    int f,s,g,u,d;
    cin >> f >> s >> g >> u >> d;
    // 총 f층
    // 나는 지금 s층
    // 나는 g층으로 하고 싶음
    // 위로 u층으로 이동하거나, 아래로 d층으로 이동
    // 만약 i+u>f거나, i-d<0이면 이동하지 않음

    queue<int> q;
    q.push(s);
    vector<int> visited(f+1, -1);
    visited[s]=0;
    while (!q.empty()){
        int current = q.front();
        q.pop();
        if (current==g) {
            cout<<visited[g]<<endl;
            return 0;
        } else {
            if ((current+u)<=f && visited[current+u]==-1) {
                visited[current+u]=visited[current]+1;
                q.push(current+u);
            }
            if ((current-d)>0&&visited[current-d]==-1) {
                visited[current-d] = visited[current]+1;
                q.push(current-d);
            }
        }
    }

    cout << "use the stairs" << endl;
    return 0;
}