[백준][C++] 5014: 스타트링크

문제 링크: https://www.acmicpc.net/problem/5014

 

정답으로 가는 조합이 여러개 생길 수 있는데 (e.g. UD, UUDD, UDDUDUDU...) 이 때 답이면서 가장 적게 버튼을 누른 방법을 구하려면 BFS를 사용하면 됩니다.

BFS는 가장 먼저 도달한 경로가 최단경로가 되기 때문에 이걸 사용해야 적절하겠죠

#include <bits/stdc++.h>
using namespace std;


bool visited[1000001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int F, S, G, U, D;
	cin >> F >> S >> G >> U >> D;


	queue<pair<int, int>> q;	// current, counter
	q.emplace(S, 0);
	visited[S] = true;
	while (!q.empty()) {
		auto [current, counter] = q.front();
		q.pop();

		if (current == G) {
			cout << counter << '\n';
			exit(0);
		}
			
		if (current + U <= F && !visited[current + U]) {
			visited[current + U] = true;
			q.emplace(current + U, counter + 1);
		}
		if (current - D > 0 && !visited[current - D]) {
			visited[current - D] = true;
			q.emplace(current - D, counter + 1);
		}
	}

	cout << "use the stairs\n";


	return 0;
}

BFS를 다 돌았을 때 G에 도달하지 못하면 계단을 써야하는 것이니 G를 찾으면 바로 exit(0)을 해줬습니다.