백준 / 5014번 / 스타트링크 / C++

#출처 : https://www.acmicpc.net/problem/5014

처음엔 DFS 로 풀다가 메모리초과 떠서 DP까지 생각해 내기 전에 BFS로 다시 풀었다.

BFS를 쓸 때 check 배열의 필요성을 못느껴서 dist배열 하나로 끝냈다.

#풀이 

#include <iostream>
#include <queue>
#define endl '\n'
#define MAX 1000005
using namespace std;
int F, S, G, U, D;
int dist[MAX];
 
bool inRange(int x)
{
    return x >= 1 && x <= F;
}
void BFS(queue<int>& q)
{
    while (q.size())
    {
        int pos = q.front();
        q.pop();
 
        int nextU = pos + U;
        if (inRange(nextU) && !dist[nextU])
        {
            dist[nextU] = dist[pos] + 1;
            q.push(nextU);
        }
 
        int nextD = pos - D;
        if (inRange(nextD) && !dist[nextD])
        {
            dist[nextD] = dist[pos] + 1;
            q.push(nextD);
        }
    }
    if (dist[G])
        cout << dist[G] - 1 << endl;
    else
        cout << "use the stairs" << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> F >> S >> G >> U >> D;
    queue<int> Q;
    Q.push(S);
    dist[S] = 1;
    BFS(Q);
    return 0;
}