[BaekJoon] 백준 5014 스타트링크

[BaekJoon] 백준 5014번 스타트링크

 

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

 

내코드

 

- 간단한 bfs문제: queue이용, 너비 우선

- 알고리즘

1. 처음 있는 위치를 큐에 넣는다.

2. 큐에서 pop을 해서 pop한 위치를 기준으로 u를 더해준 값과 d를 빼준 값을 얻는다.

2-1. 여기서 만약 가고 싶은 층과 일치하면 출력후 return

3. u를 더해준 값이 최대 층보다 커지거나 d를 빼준 값이 1보다 작아지면 안되므로 아닌 경우에만 push를 해준다. (이때 visited == false인 것도 확인. 처음 방문할때가 최소값이므로 false일때만 push해준다.)

4. 2-3을 큐가 빌때까지 반복한다.

5. 큐가 비어서 나온경우 원하는 층에 갈수 없는 경우이므로 문자열을 출력한다.

 

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int f, s, g, u, d; cin >> f >> s >> g >> u >> d;
	bool visited[1000001] = { false };
	queue<pair<int, int>> qu;
	qu.push(make_pair(s, 0));
	visited[s] = true;
	while (!qu.empty()) {
		int point = qu.front().first;
		int num = qu.front().second;
		qu.pop();
		if (point == g) {
			cout << num;
			return 0;
		}
		int up = point + u;
		int down = point - d;
		if (up <= f && visited[up] == false) {
			qu.push(make_pair(up, num + 1));
			visited[up] = true;
		}
		if (down > 0 && visited[down] == false) {
			qu.push(make_pair(down, num + 1));
			visited[down] = true;
		}
	}
	cout << "use the stairs";
	return 0;
}

 

참고