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

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

5014번: 스타트링크

백준 5014번 스타트링크를 풀었다.

 

이동하는 비용이 버튼을 누르는 횟수이므로 위로 가나 아래로 가나 비용이 똑같다.

그래서 BFS를 사용해서 풀었다.

map[i] 배열에는 i번째 층까지 가는데 드는 최소 비용을 저장한다.

visited[i] 배열은 i번째 층에 온 적이 있는지 확인하는 용도이다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <queue>

using namespace std;
#define INF 1234567890

int f, s, g, u, d;
int map[1000001];
int visited[1000001];
queue<int> q;

void BFS() {
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		
		int next = cur + u;
		if (next > 0 && next <= f && visited[next] == 0) {
			visited[next] = 1;
			map[next] = map[cur] + 1;
			q.push(next);
		}

		next = cur - d;
		if (next > 0 && next <= f && visited[next] == 0) {
			visited[next] = 1;
			map[next] = map[cur] + 1;
			q.push(next);
		}
	}
}

int main() {
	cin >> f >> s >> g >> u >> d;

	for (int i = 0; i <= f; i++)
		map[i] = INF;

	map[s] = 0;
	visited[s] = 1;
	q.push(s);
	BFS();

	if (map[g] == INF)
		cout << "use the stairs";
	else
		cout << map[g];

	return 0;
}