[백준] 5014번 스타트링크

www.acmicpc.net/problem/5014

5014번: 스타트링크

최솟값이나 최단시간이 나오면 항상 BFS부터 의심해보자.

버튼을 최소횟수만 눌러서 g층까지 가는 것이므로 BFS로 풀면 된다.

해당 층에 방문한 적이 있다면 다시 방문할 필요가 없다.

BFS는 처음에 방문했을 때가 반드시 최단시간이라는 것이 보장되어 있기 때문이다.

그리고 최고층인 f층보다 높이 갈 수 없고 최저층인 1층보다 낮게 갈 수 없으므로 현재 층 + u가 f보다 크거나 현재층 - d가 1보다 작으면 큐에 넣어주지 않는다.

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

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int f, s, g, u, d;
	cin >> f >> s >> g >> u >> d;
	vector<bool> visited(f + 1, false);
	queue<pair<int, int>> q; // 현재 층, 현재까지 누른 버튼의 횟수
	q.push(make_pair(s, 0));
	int answer = -1;
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();
		if (cur.first == g) {
			answer = cur.second;
			break;
		}
		if (!visited[cur.first]) {
			visited[cur.first] = true;
			if (cur.first + u <= f) {
				q.push(make_pair(cur.first + u, cur.second + 1));
			}
			if (cur.first - d >= 1) {
				q.push(make_pair(cur.first - d, cur.second + 1));
			}
		}
	}
	if (answer == -1) {
		cout << "use the stairs";
	}
	else {
		cout << answer;
	}
	return 0;
}