💡 너비 우선 탐색/그래프 이론/그래프 탐색
Memory 1752KB Time 0ms Code Length 773B
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
#include<stdio.h>
#include<queue>
using namespace std;
int n, k;
struct info {
int loc;
int cnt;
};
queue<info> q;
int visited[100001];
int main() {
scanf("%d %d", &n, &k);
visited[n] = 1;
q.push({ n,0 });
int result = -1;
while (!q.empty()) {
info tmp = q.front(); q.pop();
if (tmp.loc == k) {
result = tmp.cnt;
break;
}
// x + 1 / x - 1 / 2 * x
int next = tmp.loc + 1;
if (next <= 100000 && !visited[next]) {
visited[next] = 1;
q.push({ next, tmp.cnt + 1 });
}
next = tmp.loc - 1;
if (next >= 0 && !visited[next]) {
visited[next] = 1;
q.push({ next, tmp.cnt + 1 });
}
next = tmp.loc * 2;
if (next <= 100000 && !visited[next]) {
visited[next] = 1;
q.push({ next, tmp.cnt + 1 });
}
}
printf("%d\n", result);
}
이 코드는 너비 우선 탐색(BFS) 알고리즘을 사용하여 시작점부터 목표 지점까지의 최단 거리를 구하는 프로그램이다. 먼저 시작점과 목표 지점을 입력받고, 방문한 노드를 표시하기 위한 배열을 초기화한다. 그리고 시작점을 큐에 넣는다. 큐가 비어있지 않은 동안, 큐에서 하나의 노드를 꺼내서 목표 지점인지 확인하고, 아니라면 해당 노드에서 이동할 수 있는 다음 노드들을 큐에 넣는다. 그리고 해당 노드를 방문했음을 표시한다. 이 과정을 반복하여 목표 지점에 도달할 때까지의 최단 거리를 구한다. 결과값을 출력한다.
