5014 스타트링크

알고리즘 (BFS)

- 직선으로의 BFS 를 사용하면 됨
- DP를 사용하면 시간초과가 발생함.
	- 도달시 다 종료한다고 해도, 그게 최소로 간건지 몰라서 결국 더 검사해야함.

코드

#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;
}