백준 5014번: 스타트링크

[문제 링크]

5014번: 스타트링크

---

BFS를 통해 풀 수 있는 간단한 문제였다.

한 정점에서 이동할 수 있는 경우는 U버튼을 눌렀을 때와 D버튼을 눌렀을 때 두가지 경우이다.

따라서 두가지 경우를 큐에 담아주면서 현재 위치가 도착지점 G와 같아지는 순간의 이동 횟수를 출력하면 된다.

만약 가능한 모든 층을 다 탐색했는데 도착지점 G를 방문하지 못했다면 불가능하므로 "use the stairs"를 출력한다.

---

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

const int INF = 987654321;
int F, S, G, U, D;
int visited[1000001];

int bfs() {
	queue<pair<int, int>> q;
	q.push({ S, 0 });

	while (!q.empty()) {
		int here = q.front().first;
		int press = q.front().second;
		q.pop();

		if (here == G) return press;
		
		int thereUp = here + U;

		if (thereUp <= F && !visited[thereUp]) {
			visited[thereUp] = true;
			q.push({ thereUp, press + 1 });
		}

		int thereDown = here - D;

		if (thereDown > 0 && !visited[thereDown]) {
			visited[thereDown] = true;
			q.push({ thereDown, press + 1 });
		}
	}

	return INF;
}

int main(void) {
	cin >> F >> S >> G >> U >> D;
	
	int result = bfs();

	if (result == INF)
		cout << "use the stairs" << endl;
	else 
		cout << result << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 166 day