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
'알고리즘 > BOJ' 카테고리의 다른 글
백준 1238번: 파티 (0) | 2020.09.22 |
---|---|
백준 2146번: 다리 만들기 (0) | 2020.09.22 |
백준 1005번: ACM Craft (0) | 2020.09.22 |
백준 7562번: 나이트의 이동 (0) | 2020.09.21 |
백준 2589번: 보물섬 (0) | 2020.09.21 |