💡 0-1 너비 우선 탐색/너비 우선 탐색/데이크스트라/그래프 이론/그래프 탐색/최단 경로
Memory 2784KB Time 8ms Code Length 958B
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
#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
int min_time = 100000;
int visited[100001] = {0};
struct INFO {
int start;
int end;
int cnt;
};
struct cmp {
bool operator() (const INFO & b,const INFO & a) {
if (a.cnt < b.cnt) return true;
return false;
}
};
priority_queue<INFO, vector<INFO>, cmp> q;
void bfs() {
// x-1, x+1, 2x
while (!q.empty()) {
INFO now = q.top(); q.pop();
visited[now.start] = 1;
if (now.start == now.end) {
min_time = now.cnt;
break;
}
if (now.start * 2 <= 100000 && !visited[now.start * 2]) q.push({ now.start * 2,now.end,now.cnt});
if (now.start - 1 >= 0 && !visited[now.start - 1]) q.push({ now.start - 1,now.end,now.cnt + 1 });
if (now.start + 1 <= 100000 && !visited[now.start + 1]) q.push({ now.start + 1,now.end,now.cnt + 1 });
}
}
int main() {
int n, k;
scanf("%d %d", &n, &k);
getchar();
q.push({ n,k,0 });
bfs();
printf("%d\n",min_time);
}
이 코드는 주어진 시작점 n부터 목표점 k까지 도달하는데 걸리는 최소 시간을 구하는 BFS(너비 우선 탐색) 알고리즘을 구현한 것이다. 우선, INFO 구조체는 시작점, 끝점, 이동 횟수를 저장하는 역할을 한다. cmp 구조체는 우선순위 큐에서 INFO를 비교하기 위한 비교자이다.
우선순위 큐 q에 시작점 n과 이동 횟수 0을 가지는 INFO를 넣고, bfs 함수를 호출한다. bfs 함수는 q가 빌 때까지 다음을 반복한다:
q에서 INFO를 하나 꺼내서 현재 위치를 방문했음을 표시한다.
현재 위치가 목표점과 같다면 최소 시간을 업데이트하고 종료한다.
현재 위치에서 2배로 이동할 수 있는 경우, 방문하지 않은 경우에 대해 INFO를 큐에 넣는다.
현재 위치에서 1칸 왼쪽으로 이동할 수 있는 경우, 방문하지 않은 경우에 대해 INFO를 큐에 넣는다.
현재 위치에서 1칸 오른쪽으로 이동할 수 있는 경우, 방문하지 않은 경우에 대해 INFO를 큐에 넣는다.
마지막으로 main 함수에서 시작점 n과 목표점 k를 입력받고, bfs 함수를 호출하여 최소 시간을 계산하고 출력한다.
