5014 스타트링크
알고리즘 (BFS)
1
2
3
- 직선으로의 BFS 를 사용하면 됨
- DP를 사용하면 시간초과가 발생함.
- 도달시 다 종료한다고 해도, 그게 최소로 간건지 몰라서 결국 더 검사해야함.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <list>
using namespace std;
list<pair<int, int>> q;
int F, G, S, U, D;
bool check[1000001];
int main() {
cin >> F >> S >> G >> U >> D;
q.push_back({ S, 0 });
check[S] = true;
bool canGo = false;
while (!q.empty()) {
int c = q.front().first, deep = q.front().second;
q.pop_front();
if (c == G) {
cout << deep << endl;
canGo = true;
break;
}
if (c + U <= F && !check[c+U]) {
q.push_back({ c + U, deep + 1 });
check[c + U] = true;
}
if (c - D >= 1 && !check[c-D]) {
q.push_back({ c - D, deep + 1 });
check[c - D] = true;
}
}
if (!canGo)
cout << "use the stairs" << endl;
}