백준 / 5014 스타트링크 C++

www.acmicpc.net/problem/5014

5014번: 스타트링크

간단한 bfs 문제였다. 해당 층으로 엘리베이터가 움직일 수 있으면 가능한 최소의 경우를 구하고 아니면 계단으로 가라하면 된다.

 

처음에는 누른 횟수를 계산하는 계산하는 식도 하나 추가하여 했는데 시간초과가 떴다. (왜??????)

그리하여 어짜피 bfs를 이용하므로 해당 층에 도착한 경우가 뒤늦게 도착한 경우보다 큰 값일수는 없으므로 그냥 해당 층에 도착했는지만 파악하여 돌리니 컴파일러가 자꾸 계단으로 가라를 출력했다. 도저히 틀린 곳을 찾을 수 없어 다른 분들의 풀이와 비교해보니 전혀 다른 점을 느끼지 못했다. 그래서 그냥 제출해봤는데 통과했다. 노트북을 3년 정도 쓰다보니 얘도 맛이 간거 같다. 맥북 사고 싶다.... 

 

코드는 다음과 같다.

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

int main()
{
	int f, s, g, u, d;
	string fail = "use the stairs";
	vector<bool>check;
	int result = -1;
	int now = 0;
	int cnt = 0;

	cin >> f >> s >> g >> u >> d;
	check.resize(f + 1, false);
	
	queue<pair<int, int>>q;
	q.push({ s,0 });
	check[s] = true;

	while (!q.empty())
	{
		now = q.front().first;
		cnt = q.front().second;
		q.pop();

		if (now == g) {
			result = cnt;
			break;
		}

		if ((now + u) >= 1 && (now + u) <= f) {
			if (!check[now + u]) {
				q.push({ now + u,cnt + 1 });
				check[now + u] = true;
			}
		}

		if ((now - d) >= 1 && (now - d) <= f) {
			if (!check[now - d]) {
				q.push({ now - d,cnt + 1 });
				check[now - d] = true;
			}
		}
	}

	if (result == -1)
		cout << fail;
	else
		cout << result;
}