💡 너비 우선 탐색/그래프 이론/그래프 탐색
Memory 2408KB Time 16ms Code Length 1015B
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
struct INFO
{
int n;
int t;
};
int visited[100001] = {0};
int memo[100001];
int n, k;
int min_time;
queue<INFO> q;
int result;
void bfs() {
// x-1, x+1, 2x
while (!q.empty()) {
int now = q.front().n;
int t = q.front().t; q.pop();
if (now == k) {
result = t;
return;
}
int go[3] = { now + 1, now - 1, now * 2 };
for (int i = 0; i < 3; i++) {
int next = go[i];
if (next >= 0 && next <= 100000 && !visited[next]) {
visited[next] = 1;
memo[next] = now;
q.push({ next,t+1});
}
}
}
}
int main() {
scanf("%d %d", &n, &k);
getchar();
q.push({ n, 0});
visited[n] = 1;
bfs();
printf("%d\n", result);
stack<int> result2;
int last_num = k;
result2.push(last_num);
for (int i = 0; i < result; i++) {
last_num = memo[last_num];
result2.push(last_num);
}
for (int i = 0; i < result +1; i++) {
int tmp = result2.top(); result2.pop();
printf("%d ", tmp);
}
}
이 코드는 너비 우선 탐색(BFS)을 사용하여 시작점부터 목표점까지 가는 최단 경로를 찾는 프로그램이다.
시작점과 목표점을 입력받고, 큐에 시작점과 이동 횟수 0을 넣는다.
큐가 빌 때까지 다음을 반복한다:
- 큐에서 하나를 꺼내서 현재 위치와 이동 횟수를 얻는다.
- 현재 위치가 목표점과 같다면 결과로 이동 횟수를 저장하고 종료한다.
- 현재 위치에서 x-1, x+1, 2x로 이동할 수 있는지 확인하고, 가능하다면 방문 표시를 하고 큐에 넣는다.
결과로 얻은 이동 횟수를 출력하고, 스택을 이용하여 경로를 역추적하며 출력한다.
