[C++] 백준 5014번 스타트링크

www.acmicpc.net/problem/5014

5014번: 스타트링크

처음엔 dfs로 해결하려고 문제를 접근했지만 원하는 층에 접근하지 못하는 경우가 있기에 이 부분을 조절할 수 없을 것

같아서 포기했다.

 

알고리즘 분류를 보지않고 풀려고 했는데 결국 실패하고 분류를 본 후에 bfs임을 알고 문제를 풀 수 있었다ㅠㅠ

 

문제 분류를 안 후에는 그냥 전형적인 bfs문제라서 편하게 반복문안에 엘베가 위로 올라가는 경우와 내려가는 경우를 모두 고려해서 풀 수 있었다.

 

쉬운 문제였지만 문제를 보고 알고리즘을 파악하는 방법을 더 키워야 할 것 같다!

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

queue<int> q;
int ans, cnt;
int F, S, G, U, D;

void bfs(int S, vector<int> &v) {
	v[S] = 1;
	q.push(S);
	while (!q.empty()) {
		int s = q.size();
		for (int i = 0; i < s; i++) {
			int x = q.front();
			q.pop();
			if (x == G) {
				ans = cnt;
				return;
			}
			if (x + U <= F && v[x + U] == 0) {
				v[x + U] = 1;
				q.push(x + U);
			}
			if (x - D >= 1 && v[x - D] == 0) {
				v[x - D] = 1;
				q.push(x - D);
			}
		}
		cnt++;
	}
	return;
}

int main() {
	cin >> F >> S >> G >> U >> D;
	vector<int> visit(F+1);
	bfs(S, visit);
	if (S == G) {
		cout << 0;
	}
	else {
		if (ans == 0) {
			cout << "use the stairs";
		}
		else {
			cout << ans;
		}
	}
	return 0;
}