(백준 5014번 스타트링크 C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 5

백준 5014번

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

5014번: 스타트링크

 

BFS로 풀면 좋을 것 같다는 생각을 가지고 풀면 잘 풀리는 문제!

라이님 블로그를 보니 BFS문제도 분류되어 있어 어렵지 않게 풀었다.

 

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

class elevator {
public: 
	int F, S, G, U, D, MAX_N;
	vector<int> v;

	elevator(int F, int S, int G, int U, int D) : F(F), S(S), G(G), U(U), D(D) {
		v.resize(F + 1);
		fill(v.begin(), v.end(), -1);
	}
	void bfs() {
		v[S] = 0; bfs(S);
		if (v[G] == -1) cout << "use the stairs";
		else cout << v[G];
	}
private:
	void bfs(int curr) {
		queue<int> Q;
		Q.push(curr);

		while (!Q.empty()) {
			curr = Q.front();
			Q.pop();

			if (curr + U <= F && v[curr + U] == -1) {
				v[curr + U] = v[curr] + 1;
				Q.push(curr + U);
			}
			if (curr - D > 0 && v[curr - D] == -1) {
				v[curr - D] = v[curr] + 1;
				Q.push(curr - D);
			}
		}
	}
};

int main() {
	int F, S, G, U, D; cin >> F >> S >> G >> U >> D;

	if (U == 0 && D == 0) {
		if (S != G) { cout << "use the stairs"; return 0; }
		cout << "0"; return 0;
	}

	elevator ev(F, S, G, U, D);
	ev.bfs();
	return 0;
}

 

확실히 class로 만들어서 푸니 간결해서 디버깅하기도 좋다!

앞으로도 깔끔하게 푸는 습관을 만들 수 있도록 많은 분들의 코드를 참고해야지!!

 

 

+ 난이도를 알아보기 위해 solved ac를 켰다. 이 문제는 실버 1의 문제!!

 

https://www.youtube.com/watch?v=BfWqUjunXXU

ㅎㅎ 이 노래가 생각나는군여,,ㅎㅎ