백준 5014: 스타트링크

문제 요약

엘리베이터의 상승 및 하강으로 움직일 수 있는 층 수가 주어지면, 현재 층에서 목적지층으로 갈 수 있는 최소의 버튼 수를 출력한다. 만일 엘리베이터 도착할 수 없을 경우, use the stairs를 출력한다.

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS

문제 풀이

최소 횟수를 만족하는 탐색이므로 BFS로 푸는 것이 합리적일 것이다.

예를들어 D버튼 하나면 도착하는 것을 UUDDD로도 도착하게 된다면, 답이 5가 되어버리고 만다.

BFS의 함수를 만들어서, 불가능한 경우 -1을 반환하게 하여 불가능한 경우의 처리를 가능케 했다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

int f, s, g, u, d;
bool visited[1000001] = { false };

int bfs(int num)
{
	queue<int> q;
	int level = -1, qsize;
	q.push(num);
	while (!q.empty()) {
		qsize = q.size();
		level++;
		while (qsize--) {
			auto t = q.front();
			q.pop();
			if (t == g || t == g) return level;
				if (t + u <= f && !visited[t + u]) {
					visited[t + u] = true;
					q.push(t + u);
				}
			if (t - d >= 1 && !visited[t - d]) {
				visited[t - d] = true;
				q.push(t - d);
			}
		}
	}
	return -1;
}

int main()
{
	cin >> f >> s >> g >> u >> d;

	int res = bfs(s);
	if (res >= 0) printf("%d", res);
	else printf("use the stairs");
	return 0;
}