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

비교적 쉬운 문제이다. 최단경로!!!! 이기 때문에 고민없이 BFS로 풀이를 시작했다.

 

발그림

 

1) 이 문제는 1차원 bfs문제이다.

2) bfs의 종료조건은 원하는 층에 도달했을 때

3) queue에 담는 조건은 최저층~최고층사이 이면서 방문한 적이 없는 애들

 

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


int F, S, G, U, D;
int dx[] = {0, 0};
int visit[1000001];
void bfs(int x, int d) {

	queue<pair<int, int>> q;
	visit[x] = 1;
	q.push(make_pair(x, d));


	while (!q.empty()) {
		int cx = q.front().first;
		int depth = q.front().second;
		q.pop();
		//cout << cx << "," << depth << endl;

		//종료조건: 원하는 층에 도달했을 때
		if (cx == G) {
			cout << depth;
			return;
		}

		for (int i = 0; i < 2; i++) {
			int nx = cx + dx[i];
			if (1 <=nx && nx<=F && visit[nx]==0) {
				visit[nx] = 1;
				int nd = depth + 1;
				q.push(make_pair(nx, nd));
			}
			

		}
	}
	cout << "use the stairs";
	return;
}
int main() {

	cin >> F >> S >> G >> U >> D;
	dx[0] = U;
	dx[1] = -D;
	bfs(S, 0);

	return 0;
}

 

#include<iostream>
#include<queue>

using namespace std;

//#define MAX 1000000

int visit[1000001];
int F, G, S, U, D;
queue<pair<int, int>> q;
void bfs(int x) {

	q.push(make_pair(x,0));
	visit[x] = 1;
	while (!q.empty()) {

		int cx = q.front().first;
		int cnt = q.front().second;
		q.pop();

		if (cx == G) {
			cout << cnt;
			return;
		}

		int nx_up = cx + U;
		int nx_down = cx - D;
		if (nx_up <= F && visit[nx_up] == 0) {
			visit[nx_up] = 1;
			q.push(make_pair(nx_up, cnt + 1));
		}
		if (nx_down >= 1 && visit[nx_down] == 0) {
			visit[nx_down] = 1;
			q.push(make_pair(nx_down, cnt + 1));
		}
	}

	cout << "use the stairs";
	return;

}
int main() {

	cin >> F >> S >> G >> U >> D;

	bfs(S);
	return 0;
}