5014 스타트링크

백준 5014번 문제

문제

강호는 코딩 교육을 하는 스타트업 TeachMeToCode를 운영하고 있다. 이 스타트업은 코딩을 전혀 모르는 사람들에게 코딩을 가르치는 것으로 유명하다.

강호는 새로운 교육 프로그램을 개발하고 있다. 이번에는 코딩을 할 때에 불필요한 이동을 최소화하도록 교육하는 것이다.

교육생들은 현재 1번 위치에 있고, 강의실은 총 F층 있는 건물의 G호에 위치하고 있다. 각각의 층은 건물의 왼쪽에 있는 1번 버튼과 건물의 오른쪽에 있는 2번 버튼으로 이동할 수 있다. 현재 위치가 U층이면, U+1층으로 올라가는 것을 1번 버튼, U-1층으로 내려가는 것을 2번 버튼이라고 한다. U+F층보다 높은 층으로는 이동할 수 없고, 1층보다 낮은 층으로도 이동할 수 없다.

강호는 교육생들이 강의실로 이동하는데 필요한 최소한의 버튼 조작 횟수를 알고 싶어한다. 강호를 도와줄 프로그램을 작성하시오.

입력

첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ 1000000, 0 ≤ U, D ≤ 1000000, 1 ≤ F ≤ 1000000) 각각의 숫자는 서로 다르며, S ≠ G이다.

출력

첫째 줄에 교육생들이 강의실로 이동할 때 필요한 최소한의 버튼 조작 횟수를 출력한다. 만약, 엘리베이터로 이동할 수 없을 때는 "use the stairs"를 출력한다.

예제 입력 1

10 1 10 2 1

예제 출력 1

use the stairs

예제 입력 2

100 2 1 1 0

예제 출력 2

use the stairs

예제 입력 3

100 2 1 1 1

예제 출력 3

정답


#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <list>

using namespace std;

#define MAX 1000001

int F, S, G, U, D, answer;
vector<vector<int>> edge(MAX, vector<int>());
vector<int> parent(MAX,-1);

void Input()
{
    cin >> F >> S >> G >> U >> D;
    for (int i = 0; i <= F; i++)
    {
        if (i + U < MAX)
            edge[i].push_back(i + U);
        if (i - D > 0)
            edge[i].push_back(i - D);
    }
}


void Bfs(int here)
{
    queue<int> q;
    vector<bool> visited = vector<bool>(MAX, false);
    q.push(here);
    visited[here] = true;
    while (!q.empty())
    {
        here = q.front();
        q.pop();
        if (here == G) break;
        for (int i = 0; i < edge[here].size(); i++)
        {
            int there = edge[here][i];
            if (!visited[there])
            {
                visited[there] = true;
                parent[there] = here;
                q.push(there);
            }
        }
    }
}
void Solution()
{
    Bfs(S);
    if (S == G)
    {
        cout << answer << '\n';
        return;
    }
    if (parent[G] == -1)
    {
        cout << "use the stairs" << '\n';
        return;
    }
    int here = G;
    while (here != S)
    {
        here = parent[here];
        answer++;
    }
    cout << answer << '\n';
}

void Solve()
{
    Input();
    Solution();

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    answer = 0;
    Solve();
}

좀 빡샜다.

반례를 여러가지를 고려 했어야 했다.

if (S == G) { cout << answer << '\n'; return; }

요 부분 100 , 1 , 1 , 0 , 0 이라도 0을 리턴 해줬어야 했다.

for (int i = 0; i <= F; i++) 요부분 1,000,000 1,000,000 1 0 1 이 부분도 i ≤ F를 해주지 않아서 발생했던 에러였다

if (i - D > 0) edge[i].push_back(i - D); 이부분도 i - D ≥ 0 을 했었는데 0 은 예외 했어야 했다..