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

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

5014번: 스타트링크

풀이법

1) 두개의 배열과 bfs를 활용하면 쉽게 풀 수 있는 문제이다.

2) 현재의 값을 queue에 차근 차근 넣고, now+u>f 일경우 continue로 배열에 넣지 않는다.

3) now-d<0일 경우 또한 continue를 활용하여 넣지 않고, 원하는 값인 g와 현재의 값인 now가 같게되면 값을 출력, queue가 빌때 까지 값을 찾지 못할 경우 use the stairs를 출력해 준다.

#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <math.h>
#include <map>
#include <set>
using namespace std;
int f, s, g, u,d;
int arr[1000001];
bool visited[1000001];
void bfs()
{
	queue<pair<int, int>> q;
	visited[s] = true;
	q.push({ s,0 });
	while (!q.empty())
	{
		int now = q.front().first;
		int cnt = q.front().second;
		q.pop();
		if (now == g)
		{
			cout << cnt;
			return;
		}

		if (now + u > f)
			continue;
		if (visited[now + u] == false)
		{
			visited[now + u] =true;
			q.push({ now + u,cnt + 1 });
		}

	
		if (now - d < 0)
			continue;
		if (visited[now - d] == false)
		{
			visited[now - d] = true;
			q.push({ now - d,cnt + 1 });
		}
	
	}
	cout << "use the stairs";
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> f >> s >> g >> u >> d;
	bfs();
}