스타트링크 5014

문제

접근 방법

쉬운 BFS 문제이다. 위, 아래로 가면서 값을 갱신해주면 된다고 생각했다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int F, S, G, U, D;
    queue<int> bfs;
    cin >> F >> S >> G >> U >> D;
    vector<int> floors(F + 1);
    floors[S] = 1;
    bfs.push(S);
    while (!bfs.empty())
    {
        int cur = bfs.front();
        if (cur == G)
            break;
        bfs.pop();
        int up = cur + U, down = cur - D;
        if (up <= F && !floors[up])
        {
            floors[up] = floors[cur] + 1;
            bfs.push(up);
        }
        if (down >= 1 && !floors[down])
        {
            floors[down] = floors[cur] + 1;
            bfs.push(down);
        }
    }
    if (bfs.empty())
        cout << "use the stairs";
    else
        cout << floors[bfs.front()] - 1;
    return 0;
}

풀이

이 문제에 무서운 점은 시작점을 0으로 두어서는 안 된다는 것이다. 만약 시작점을 방문했다고 표시 안 한다면 U와 D가 0일 때 제자리걸음을 하기에 틀릴 수밖에 없다는 것이다. (쓸데없이 1이 더 늘어난다)
문제의 조건을 잘 보고 푸는 것이 중요하다는 것을 다시 느낀다.