Newer
Older
---
layout : wiki
title : SWEA 4112. 이상한 피라미드 탐험
summary :
date : 2021-01-27 10:38:42 +0900
updated : 2021-12-15 18:09:08 +0900
tag : bfs
public : true
published : true
parent : [[swea]]
latex : false
---
* TOC
{:toc}
- 6방향이 있고, depth를 통해 계산할 수 있다.
- 최소 시간을 구해야 하기 때문에 bfs를 이용한다.
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
using namespace std;
#define MAX_N 10005
int tc;
int from, to;
int res;
int depth[MAX_N];
bool visited[MAX_N];
void init() {
memset(visited, 0, sizeof(visited));
scanf("%d%d", &from, &to);
}
void prepare() {
int i = 1;
int curDepth = 1;
while (i < MAX_N) {
for (int j = 0; j < curDepth; i++, j++) {
if (i >= MAX_N) break;
depth[i] = curDepth;
}
curDepth++;
}
}
int bfs() {
queue<int> q;
q.push(from);
visited[from] = true;
int cnt = 0;
while (!q.empty()) {
int qSize = q.size();
for (int qs = 0; qs < qSize; qs++) {
int cur = q.front();
q.pop();
if (cur == to)
return cnt;
int next;
// left-top
next = cur - depth[cur];
if (!visited[next] && depth[next] == depth[cur] - 1) {
visited[next] = true;
q.push(next);
}
// right-top
next = cur - depth[cur] + 1;
if (!visited[next] && depth[next] == depth[cur] - 1) {
visited[next] = true;
q.push(next);
}
// left
next = cur - 1;
if (!visited[next] && depth[next] == depth[cur]) {
visited[next] = true;
q.push(next);
}
// right
next = cur + 1;
if (!visited[next] && depth[next] == depth[cur]) {
visited[next] = true;
q.push(next);
}
// left-bottom
next = cur + depth[cur];
if (!visited[next] && depth[next] == depth[cur] + 1) {
visited[next] = true;
q.push(next);
}
// right-bottom
next = cur + depth[cur] + 1;
if (!visited[next] && depth[next] == depth[cur] + 1) {
visited[next] = true;
q.push(next);
}
}
cnt++;
}
return 0;
}
int main() {
prepare();
int testcase;
scanf("%d", &testcase);
for (tc = 1; tc <= testcase; tc++) {
init();
printf("#%d %d\n", tc, solution());
}
}
```