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

문제

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

5014번: 스타트링크

문제풀이

다른 문제가 더 있는지는 모르겠지만 큐에 집어넣기 전에 visit과 정답을 확인하냐 안 하냐에 따라서 메모리 초과가 갈렸다.

BFS로 풀었고 큐를 pair로 선언하여 현재 위치, 버튼을 누른 횟수를 push 했다.

visit벡터를 이용해서 두 번 다시 같은 층을 가지 않도록 했다.

평범한 BFS문제인 것 같다. 크게 신경 써야 할 건 없는 것 같다.

처음 시작층과 0을 큐에 집어넣고 큐가 빌 때까지 while문을 반복한다.

다음 층은 U층 올라간 층 또는 D층 내려간 층이 된다.

다음 층이 G층인지, 건물보다 높은 층이 아닌지, 1층 보다 더 낮은 층인지, 방문을 하지 않았는지를 확인한다.

큐가 빌 때까지 G층에 도착하지 못하면 계단을 이용해야 하는 층이므로 "use the stairs"를 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<bool>visit;
int F, S, G, U, D;
vector<int>button;

void BFS() {
	queue<pair<int, int>>q;
	q.push({ S, 0 });
	visit[S] = true;
	while (!q.empty()) {
		int floor = q.front().first;
		int cnt = q.front().second;
		q.pop();		
		for (int idx = 0; idx < 2; ++idx) {
			int next_floor = floor + button[idx];
			if (next_floor == G) {
				cout << cnt + 1;
				return;
			}
			else if (next_floor >= 1 && next_floor <= F && !visit[next_floor]) {
				visit[next_floor] = true;
				q.push({ next_floor,cnt + 1 });
			}
		}
	}
	cout << "use the stairs";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> F >> S >> G >> U >> D;
	visit = vector<bool>(F + 1, false);
	button = vector<int>{ U,-D };

	if (S == G) cout << 0;
	else BFS();
}