취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 5014번 문제인 스타트링크이다.
문제는 아래 링크를 확인하자.

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

각 층을 노드로, 현재 층에서 갈 수 있는 층 방향으로의 direced edge를 간선으로 하여 각 층까지 엘리베이터를 이용해야하는 최소 횟수, 즉 최단거리를 구해보자.

이 때, 모든 에지의 가중치가 같으므로 BFS를 이용하여 빠르게 최단거리를 구할 수 있다.

아래는 제출한 소스코드이다.

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

int F, S, G, U, D;
int dist[1000001];

void bfs() {
	dist[S] = 1;
	queue<int> que;
	que.push(S);

	while (!que.empty()) {
		int cur = que.front();
		que.pop();
		int curU = cur + U, curD = cur - D;
		if (curU <= F) {
			if (dist[curU] == 0) {
				dist[curU] = dist[cur] + 1;
				que.push(curU);
			}
		}
		if (curD > 0) {
			if (dist[curD] == 0) {
				dist[curD] = dist[cur] + 1;
				que.push(curD);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

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

	bfs();

	if (dist[G] == 0) cout << "use the stairs";
	else cout << dist[G] - 1;
}