💡 너비 우선 탐색/그래프 이론/그래프 탐색
Memory 4956KB Time 12ms Code Length 1112B
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
#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
int min_time = 100000;
int way = 0;
int visited[100001] = {0};
struct INFO {
int start;
int end;
int cnt;
};
queue<INFO> q;
void bfs() {
// x-1, x+1, 2x
while (!q.empty()) {
INFO now = q.front(); q.pop();
visited[now.start] = 1;
if (min_time < now.cnt)break;
if (now.start == now.end) {
visited[now.start] = 0;
// 현재 카운트가 최소값보다 작으면 최솟값 갱신
if (min_time > now.cnt) {
min_time = now.cnt;
way = 1;
}
// 현재 카운트가 최솟값과 같으면
else if (min_time == now.cnt) {
way++;
}
}
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 });
if (now.start * 2 <= 100000 && !visited[now.start * 2]) q.push({ now.start * 2,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);
printf("%d\n",way);
}
이 코드는 너비 우선 탐색(BFS) 알고리즘을 사용하여 시작점에서 목표 지점까지 이동하는 최단 시간과 그 최단 시간으로 이동하는 방법의 수를 계산하는 프로그램이다.
시작점에서 목표 지점까지 이동하는 최단 시간을 찾기 위해 BFS 알고리즘을 사용한다.
방문한 노드를 표시하기 위해 visited 배열을 사용한다.
INFO 구조체는 현재 위치(start), 목표 위치(end), 그리고 이동한 횟수(cnt)를 저장한다.
큐(q)에 시작점에서 시작하는 INFO 구조체를 넣고 BFS를 시작한다.
큐가 빌 때까지 다음 작업을 반복한다.
- 큐에서 현재 위치를 꺼내고 방문 표시를 한다.
- 최단 시간을 넘어가면 종료하고, 목표 지점에 도달하면 최단 시간과 방법의 수를 갱신한다.
- 현재 위치에서 이동할 수 있는 경우를 확인하고, 방문하지 않은 경우에는 큐에 추가한다.
BFS가 종료되면 최단 시간과 방법의 수를 출력한다.
