[백준OJ] 5014번 스타트링크

https://www.acmicpc.net/problem/5014

5014번: 스타트링크

---

 

 

 

-풀이-

BFS를 이용하여, 모든 경우중 최소횟수로 갈 수 있는 경우들을 구한 뒤, 만약 G층에 도달한다면 그 횟수를, 도달하지 못했다면 "use the stairs"를 출력해준다.

 

-시간복잡도-

모든 층을 검사하므로, O(F)가 된다.

 

-코드-

#include <iostream>
#include<algorithm>
#include<queue>
using namespace std;

int F, S, G, U, D;

void updown() {
	bool visited[1000001] = { 0 };
	queue<pair<int, int>> q;
	q.push({ S,0 });

	while (!q.empty()) {
		int now = q.front().first;
		int cnt = q.front().second;
		q.pop();

		if (now == G) {
			cout << cnt << "\n";
			return;
		}

		if (now + U <= F && !visited[now + U]) {
			q.push({ now + U,cnt + 1 });
			visited[now + U] = true;
		}
		if (now - D >= 1 && !visited[now - D]) {
			q.push({ now - D,cnt + 1 });
			visited[now - D] = true;
		}
	}
	cout << "use the stairs\n";
	return;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> F >> S >> G >> U >> D;
	updown();
	return 0;
}