[C/C++] BOJ 5014 :: 스타트링크

BOJ 5014 :: 스타트링크

문제 링크 : https://www.acmicpc.net/problem/5014

나의 풀이

예외조건을 제외하고 넓이우선탐색으로 최소 버튼 수를 도출한다.

* 예외조건*

1) 현재층 = 도착층일 때, 0 출력

2) 현재층 > 도착층인데 아래층으로 갈 수 없을 때

3) 현재층 < 도착층인데 윗층으로 갈 수 없을 때

4) 윗층과 아래층 모두 갈 수 없을 때 

use the stairs 출력

bfs탐색한 후, G에 도착가능할 때, 최소 버튼 수 출력

G에 도착가능하지 않을 때, use the stairs 출력

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_5014/BOJ_5014.cpp

// BOJ 5014 :: 스타트링크
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
 
int F, S, G, U, D, ret;
bool flag;
int visited[1000001];
vector<int> v;
 
void bfs(int _S)
{
    queue<int> q;
    q.push(_S);
    visited[_S] = 1;
 
    while (!q.empty())
    {
        int qsz = q.size();
        while (qsz--)
        {
            int cur = q.front();
            q.pop();
 
            if (cur == G) { flag = true;  return; };
 
            for (int i = 0; i < (int)v.size(); i++)
            {
                int mcur = cur + v[i];
 
                if (mcur < 1 || mcur > F) continue;
                if (visited[mcur]) continue;
                q.push(mcur);
                visited[mcur] = 1;
            }
        }
        ret++;
    }
    return;
}
 
int main() {
 
    cin >> F >> S >> G >> U >> D;
    if (U != 0) v.push_back(U);
    if (D != 0) v.push_back(-D);
    
    if (S != G)
    {
        if ((S > G && D == 0) || (S < G && U == 0) || (U == 0 && D == 0))
        {
            cout << "use the stairs";
        }
        else
        {
            bfs(S);
            if (flag) cout << ret;
            else cout << "use the stairs";
        }
    }
    else cout << "0";
 
    return 0;
}