백준 5014번: 스타트링크 (C++)

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

5014번: 스타트링크

 

1차원에서 최단거리를 구하는 문제이고, 가중치가 없기 때문에 bfs를 활용해주면 된다.

 

움직임 배열을 입력받는 U와 D로 정해주고, 시작점을 큐에 넣은 이후에, 하나씩 pop 해서 확인해주면 된다.

 

#include<iostream>
#include<queue>
using namespace std;
int n, src, des, Up, Down;
int dis[1000001]; //1 indexed
int Move[2];
queue<int> q;
void bfs(int start) {
	q.push(start);
	dis[start]++;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int i = 0; i < 2; i++) {
			int nf = cur + Move[i];
			if (nf < 1 || nf > n || dis[nf] >= 0) continue;
			q.push(nf);
			dis[nf] = dis[cur] + 1;
		}
	}
}
int main(void) {
	
	cin >> n >> src >> des >> Up >> Down;
	for (int i = 1; i <= n; i++)
		dis[i] = -1;
	Move[0] = Up;
	Move[1] = Down * -1;
	bfs(src);
	if (dis[des] == -1) cout << "use the stairs\n";
	else
		cout << dis[des] << '\n';
	return 0;
}