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

문제

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

5014번: 스타트링크

 

문제이해

 

• 첫째 줄에 F, S, G, U, D를 입력한다.
• 강호가 S층에서 G층으로 가기 위해서 눌러야 하는 버튼 수의 최솟값을 출력한다. G층으로 갈 수 없다면 "use the stairs"를 출력한다.

 

S층에서 G층으로 가는 최단 거리를 찾는 문제로 너비 우선 탐색(BFS)를 이용하여 풀어야 되는 문제이다. 큐(queue)에 강호가 처음에 있는 층인 S층을 넣고 시작한다. 이후 큐(queue)의 front를 pop 하고 S + U 층와 S - D 층을 넣는 식으로 BFS를 실행한다. BFS도중 G값이 나온 경우 지금까지 눌렀던 버튼의 수의 값을 출력한다. BFS를 전부 다 돌렸는데도 G값이 나오지 않은 경우 "use the stairs"를 출력한다.

 

예시입니다.

F(10), S(2), G(5), U(2), D(1)

2

-> 강호의 처음 위치를 큐에 저장

 

4

1

-> 강호의 처음 위치를 큐에서 제거하며 2 + 2와 2 - 1을 큐에 저장

 

1

6

3

->위치 4를 큐에서 제거하며 4 + 2와 4 - 1을 큐에 저장

 

6

3

->위치 1를 큐에서 제거하며 1 + 2(중복), 1 - 1(양수 x)

 

3

8

5

->위치 6을 큐에서 제거하며 6 + 2, 6 - 1을 큐에 저장

 

이렇게 계속 진행하다가 5가 제거되는 데까지 걸리는 시간을 출력하면 된다.

 

다음은 위의 내용대로 만들어진 코드이다.

 

 

문제풀이

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

int F, S, G, U, D;

void bfs() {
	queue<pair<int,int>> go;
	vector<bool> visit(F + 1);
	go.push(make_pair(S, 0));
	visit[S] = true;
	while (!go.empty()) {
		int top = go.front().first;
		int way = go.front().second;
		if (top == G) {
			cout << way;
			return;
		}
		go.pop();
		if (top + U <= F && !visit[top + U]) {
			go.push(make_pair(top + U, way + 1));
			visit[top + U] = true;
		}
		if (top - D >= 1 && !visit[top - D]) {
			go.push(make_pair(top - D, way + 1));
			visit[top - D] = true;
		}
	}
	cout << "use the stairs";
}

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

 

 

문제후기

매우 간단한 bfs 문제였습니다.