백준 5014번 C++

백준 5014번 스타트링크

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

5014번: 스타트링크

정답 코드

#include<iostream>
#include<queue>
using namespace std;
queue<pair<int, int>>q;
int vis[2000001];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int f, s, g, u, d;
	cin >> f >> s >> g >> u >> d;
	for (int x = 0; x < 2000001; x++) {
		vis[x] = -1;
	}
	q.push({ s,0 });
	vis[s] = 0;
	while (!q.empty()) {
		int pos = q.front().first;
		int time = q.front().second;
		q.pop();
		if (pos == g) {
			cout << time;
			return 0;
		}
		int arr[2] = { pos + u,pos - d };
		for (int dir = 0; dir < 2; dir++) {
			int mp = arr[dir];
			if (mp >f||mp<=0)
				continue;
			if (vis[mp]==1)
				continue;
			q.push({ mp,time + 1 });
			vis[mp] = 1;
		}
	}
	cout << "use the stairs";
}

문제 풀이

bfs를 이용해서 풀었습니다. 이 문제는 백준의 숨바꼭질 문제와 매우 비슷하다는 느낌을 받았습니다. 시작점이 정해져 있고 보통은 큐안에 좌표를 저장하지만 이 경우에는 위치와 이동횟수를 저장하였습니다. 그래서 bfs를 돌리면서 pos==g가 되면 거기에 해당하는 이동횟수를 출력하게 하였습니다. 그게 아니라면 배열에 움직일 수 있는 범위를 저장하고 for문을 돌려서 그에 따른 위치와 이동횟수를 저장하였습니다. 그리고 지상이기 때문에 위치가 0이 될 수 없고 주어진 건물의 높이보다 높을 수 없다는 점을 주의해서 풀었습니다.