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

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

5014번: 스타트링크

풀이법

1) 방문한 곳을 체크하는 visited배열과 BFS기반의 알고리즘으로 문제를 해결했다.

2) 항상 현재 stairs 기준으로 내려가서 올라가거나, 올라간 후 내려가는 경우를 고려해야 하기에, 하나의 stairs에 가능한 down과 up 을 모두 고려해 주어야 풀 수 있다.

3) 범위를 고려하여 항상 1보다 크고 f보다 작은 칸을 이동하는 것으로 코딩을 진행하였다.

#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#define INF 987654321
using namespace std;

int f, s, g, u, d;
bool visited[1000010];
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> f >> s >> g >> u >> d;
	visited[s] = true;
	queue<pair<int, int>> q;
	q.push({ s,0 });
	bool check = false;
	while (!q.empty())
	{
		int nowStair = q.front().first;
		int cnt = q.front().second;
		q.pop();
		if (nowStair == g)
		{
			cout << cnt ;
			check = true;
			break;
		}
		int up = nowStair + u;
		int down = nowStair - d;
		if (up >= 1 && up <= f)
		{
			if (!visited[up])
			{
				visited[up] = true;
				q.push({ up,cnt + 1 });
			}
		}
		if (down >= 1 && down <= f)
		{
			if (!visited[down])
			{
				visited[down] = true;
				q.push({ down,cnt + 1 });
			}
		}
	}
	if(check==false)
		cout << "use the stairs";

}