💡 너비 우선 탐색/그래프 이론/그래프 탐색
Memory 5136KB Time 20ms Code Length 756B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<stdio.h>
#include<queue>
using namespace std;
struct info {
int now;
int cnt;
};
int F, S, G, U, D;
int visited[1000001];
queue<info> q;
int main() {
scanf("%d %d %d %d %d", &F, &S, &G, &U, &D);
q.push({S,0});
visited[S] = 1;
int result = -1;
while (!q.empty()) {
info tmp = q.front(); q.pop();
if (tmp.now == G) {
result = tmp.cnt;
break;
}
int Up_next = tmp.now + U;
if (Up_next <= F && !visited[Up_next]) {
visited[Up_next] = 1;
q.push({ Up_next, tmp.cnt + 1 });
}
int Down_next = tmp.now - D;
if (Down_next > 0 && !visited[Down_next]) {
visited[Down_next] = 1;
q.push({ Down_next, tmp.cnt + 1 });
}
}
if (result == -1) printf("use the stairs\n");
else {
printf("%d\n", result);
}
}
이 코드는 주어진 시작 위치에서 목표 위치까지 이동하는 최소 횟수를 구하는 프로그램이다. 입력으로는 건물의 총 층수, 현재 위치, 목표 위치, 올라갈 층수, 내려갈 층수가 주어진다.
이동은 올라가거나 내려가는 것으로만 가능하며, 올라가는 경우와 내려가는 경우를 각각 따로 큐에 저장하면서 BFS(너비 우선 탐색) 알고리즘을 사용하여 최소 이동 횟수를 구한다. 만약 목표 위치에 도달할 수 없는 경우 “use the stairs”를 출력하고, 도달할 수 있는 경우 최소 이동 횟수를 출력한다.
