[알고리즘 문제] 백준5014 - 스타트 링크

www.acmicpc.net/problem/5014

5014번: 스타트링크

bfs를 사용하여 문제를 해결할 수 있다. 만약 현재 강호 위치에서 위/아래로 이동할 수 있으면 그 위치를 que에 계속 넣어주고 만약 현재 위치가 도착지점이라면 그때 이동한 횟수를 출력해주면 된다. 

 

단순히 que에 넣고 빼는 과정이지만 신경써주어야 할 부분이 2가지 있다.

 

1. 현재의 que 사이즈 만큼 검사해준다.

검사를 진행하면서 계속 que에 넣는 과정이 진행되는데 이렇게 되면 하루가 어떻게 지났는지 확인할 수 없다. 그렇기 때문에 for문을 모두 반복하면 하루가 지났음을 의미하고 days++을 해준다.

 

2. 이미 방문한 위치는 check를 해준다.

이미 방문한 곳은 또다시 방문할 필요가 없다. visited[x]의 값이 1라는 의미는 앞서 이미 방문했다는 의미이고 그곳을 또다시 방문하는 것은 하루 또는 몇일이 지나고 방문한 것이기 때문이다. 예를 들어 11층을 4번만에 방문했다(여기서 방문했다는 의미는 당시의 days값이 4라는 의미). 그 이후 11층을 방문하는데 그때의 day값이 6라면 방문할 필요가 없다. 왜냐하면 우리는 최솟값을 구하기 때문이다.

 

근데 이 문제를 푸는데 생각보다 오래 걸렸다. 윗층으로 올라가는 경우의 최대값을 잘못 설정해주었는데, 처음에는 윗층으로 가는 최대값을 1000000으로 해주었다, 이 경우 틀림으로 나왔고 F로 해주니깐 제대로 풀렸다. 이후 왜 1000000으로 하면 안되는지 한번 생각해 보았다.

 

문제의 테스트 케이스에서는 상관이 없지만, 20 16 20 5 1으로 입력이 주어졌을 때 최대값을 1000000와 F 2가지로 나누어 생각해보면

1. 1000000 : 16 -> 21 > 20 : 2번만에 성공

2: 20 : 16 -> 17 -> 18 -> 19 ->20: 4번만에 성공

 

즉 실제 답은 4이지만 최대값을 잘못 수정해서 2라는 값이 출력될 것 이다.

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    int F, S, G, U, D;
    cin >> F >> S >> G >> U >> D;

    queue<int> que;
    que.push(S);
    int visited[2000001];
    visited[S] = 1;

    int days = 1;
    while (!que.empty())
    {
        int size = que.size();
        for (int i = 0; i < size; i++)
        {
            int cur = que.front();
            int toUp = cur + U;
            int toDown = cur - D;
            que.pop();

            if (cur == G)
            {
                cout << days << endl;
                return 0;
            }

            if (toUp <= F && !visited[toUp])
            {
                que.push(toUp);
                visited[toUp] = 1;
            }

            if (toDown >= 1 && !visited[toDown])
            {
                que.push(toDown);
                visited[toDown] = 1;
            }
        }
        days++;
    }

    cout << "use the stairs" << endl;

    return 0;
}