[백준/BOJ] 백준 5014번 : 스타트링크

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

5014번: 스타트링크

start위치부터 g층까지 가기 위해 누르는 버튼 횟수의 최솟값을 구하는 함수를 만들었다. g층에 도착했을 때 그 위치의 depth[here]가 버튼을 누른 횟수의 최소이다. u층 위로 올라갔을 때, d층 아래로 내려갔을 때를 bfs를 통해 구현했다.

 

코드

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

int f, s, g, u, d;
int discoverd[1000001];
int depth[1000001];

//start위치부터 g층까지 가기위해 누르는 버튼 횟수의 최솟값을 구한다
int Solve(int start)
{
	//발견되지 않은 층은 0, 발견한 층은 1로 하기 위해
	//처음에 0으로 초기화 한다
	memset(discoverd, 0, sizeof(discoverd));

	queue<int> q;

	//start위치를 발견했다고 체크
	discoverd[start] = 1;

	//start위치의 depth는 0이다
	depth[start] = 0;

	//큐에 start위치를 넣는다
	q.push(start);

	while (!q.empty())
	{
		int here = q.front();
		q.pop();

		//g층에 도착했을때, 누른 최소 버튼은 depth이다
		if (here == g)
			return depth[here];

		//u층 위로 올라가도 범위를 넘어가지 않고 그곳이 발견된적이 없는곳일때
		if (here + u <= f && discoverd[here + u] == 0)
		{
			discoverd[here + u] = 1;
			depth[here + u] = depth[here] + 1;
			q.push(here + u);
		}

		//d층 아래로 내려가도 범위를 벗어나지 않고 그곳이 발견된적이 없는곳일때
		if (here - d >= 1 && discoverd[here - d] == 0)
		{
			discoverd[here - d] = 1;
			depth[here - d] = depth[here] + 1;
			q.push(here - d);
		}
	}

	//g층에 도달할 수 없을때
	return -1;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int result;

	cin >> f >> s >> g >> u >> d;

	result = Solve(s);

	if (result == -1)
		cout << "use the stairs";
	else
		cout << result;

	return 0;
}