백준 5014번 스타트링크 (C++)

 전형적인 bfs문제이다.

bfs의 근거는 다음과 같다.

1. 최소값을 구한다.

2. 갈수있는 방향과 칸수가 정해져있다.

 

그리고 조심해야할 점으로는 빌딩의 층을 넘어가면 아에 동작하지 않아야하는 것과 빌딩에는 0층이 없다 는 것을 간과해선 안된다. 그리고 c++ 에서 배열의 최댓값은 컴파일러에 따라 다르지만 VS의 경우 1메가바이트 = 1백만 바이트이기 때문에 거리를 저장할 배열을 정적으로 선언해놓는 것이 힘들다. 때문에 동적할당을 통해 거리와 방문여부를 체크할 배열을 만들었다.

 

 

#include <iostream>
#include <queue>

using namespace std;


int main() {
	int F, S, G, U, D;
	queue<int> q;
	cin >> F >> S >> G >> U >> D;
	int* dis = new int[F + 1];
	bool* visited = new bool[F + 1];

	for (int i = 0; i <= F; i++) {
		dis[i] = 0;
		visited[i] = false;
	}
	q.push(S);
	visited[S] = true;
	while (!q.empty()) {
		int X = q.front();
		q.pop();

		if (X == G) {
			cout << dis[G] << '\n';
			return 0;
		}

		int nextU = X + U;
		int nextD = X - D;

		if (nextU <= F && visited[nextU] == false) {
			visited[nextU] = true;
			q.push(nextU);
			dis[nextU] = dis[X] + 1;
		}

		if (nextD > 0 && visited[nextD] == false) {
			visited[nextD] = true;
			q.push(nextD);
			dis[nextD] = dis[X] + 1;
		}
	}

	cout << "use the stairs" << '\n';

	return 0;
}