[백준 5014번] 스타트링크

풀이

---

재귀로 풀려고 했지만 크기가 커서 스택 오버플로우를 맞이할 수도있겠다는 생각이 들었다.

--> 메모이제이션을 사용하면 풀수도 있을것같다.

갈수 있는 방법을 모두 가되 중복되지 않게 이동하는 하는 방법에 대해 생각해보면 BFS를 통해 풀수있다는 것을 알 수 있었다.

현재 층에서 아래로 갔을 경우, 위로 갔을 경우 큐에 삽입해두고, 하나씩 꺼내면서 목표한 층이 맞는지 비교해보면 된다.

소스 코드

---

#include <iostream>
using namespace std;
// f -> 전체 층수
// s -> 현재 층
// g -> 가려고 하는 층
// u -> up버튼을 눌렀을때 이동하는 층수
// d -> down버튼을 눌럿을때 이동하는 층수
 
int f, s, g, u, d, flag, cnt;
int que[1000001],head=0,tail=0;
int visit[1000001] = { 0, };
int c_que[1000001], c_head = 0, c_tail = 0;
 
void push(int a, int c) {
    que[tail++] = a;
    c_que[c_tail++] = c;
}
 
int pop() {
    return que[head++];
}
 
int c_pop() {
    return c_que[c_head++];
}
 
void bfs() {
    while (1) {
        int cur = pop();
        int cur_cnt = c_pop();
 
        if (cur == g) {
            flag = 0;
            cnt = cur_cnt;
            break;
        }
        if (cur + u <= g && visit[cur+u] == 0) {
            push(cur + u, cur_cnt + 1);
            visit[cur + u] = 1;
        }
        if (cur - d >= 0 && visit[cur-d] == 0) {
            push(cur - d, cur_cnt + 1);
            visit[cur-d] = 1;
        }
        if (head == tail) {
            flag = 1;
            break;
        }
    }
}
 
int main() {
    cin >> f >> s >> g >> u >> d;
    push(s, 0);
    bfs();
    if (flag)
        cout << "use the stairs" << '\n';
    else if (!flag)
        cout << cnt << '\n';
    return 0;
}