-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathkdtree
83 lines (26 loc) · 4.03 KB
/
kdtree
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
k-d트리는 다차원의 점들(자료들)을 저장하기 위한 자료구조입니다. 알아보기 전에 먼저 저보다 훨씬 잘 설명해둔 사이트를 링크해둘게요.
https://en.wikipedia.org/wiki/K-d_tree
k-d tree - Wikipedia
A 3-dimensional k-d tree. The first split (the red vertical plane) cuts the root cell (white) into two subcells, each of which is then split (by the green horizontal planes) into two subcells. Finally, four cells are split (by the four blue vertical planes
en.wikipedia.org
그냥 여기만으로 이해하는 게 훨씬 편하지 않을까요?
그럼 이제부터 k-d 트리에서 어떻게 점을 저장하는지 알아보도록 합시다. 먼저 k-d tree는 이진트리 구조로 되어있다는 점은 알아두세요.
k차원의 점들이 N개 존재한다 합시다. 먼저 우리는 N개의 점들을 X좌표를 기준으로 나누어주어야 합니다. 적절하게 나누기 위해서는 그 점들의 x좌표의 중앙값을 기준으로 나누는 게 제일 적절하겠죠. 중앙값은 그냥 점들 전체를 정렬하면 O(NlogN)에 구할 수 있습니다. 더 빠르게도 구할 수 있다고 하는데, 그건 좀 논점 밖이죠.
그리고 그 노드에는 그 x좌표의 중앙값에 해당하는 점을 배치하고 그 점보다 x좌표가 작은 점들은 왼쪽, 그 점보다 x좌표가 큰 점들은 오른쪽으로 갑니다.
그리고 이제 다시 점들을 나눠줘야 되는데, 또 x좌표로 정렬하는 걸까요? 아니에요. 그러면 x좌표가 모두 같을 때는 트리가 너무 비효율적인 구조로 만들어지겠죠. 대신 우리는 y좌표를 기준으로 하여 점들을 정렬해줍니다.
왼쪽에서도 y좌표를 기준으로 정렬해서 중앙값 기준으로 나눠주고, 오른쪽에서도 y좌표 기준으로 정렬해서 중앙값 기준으로 나눠줍니다.
그리고 또 점들은 더 밑으로 내려오겠죠. 그럼 그 점들은 이제 z좌표를 기준으로 나눠주면 되요! 물론 3차원 이상의 점이 아니라면 다시 x좌표 기준으로 나눠줘요.
이거를 정리하자면,
점들의 차원이 k차원이고 현재 depth가 x일 때, (x%k) 번째 차원을 기준으로 점들을 나눠줍니다. (깊이와 차원은 모두 0-based)
2차원에서 k-d tree를 나타낸 그림을 보여드릴게요.
2차원에서의 k-d tree
저 그림에서 어떻게 k-d tree가 구축되는지 알아봅시다. 먼저 모든 점들을 봅시다. (2,3),(4,7),(5,4),(8,1),(9,6),(7,2)가 있네요. x좌표 순으로 정렬하면 (2,3),(4,7),(5,4),(7,2),(8,1),(9,6)입니다. 자료가 짝수 개인데 중앙값은 평균으로 뽑아야 될까요? 아니요. 그냥 3번째나 4번째 중에 맘에 드는 거 뽑아요. 저는 4번째인 (7,2)를 뽑을게요.
그리고 깊이를 한 단계 내려갑시다. 왼쪽으로는 점 (2,3),(4,7),(5,4)이 내려오네요. y좌표 기준으로 정렬했을 때 중간은 (5,4)이고 y좌표가 작은 (2,3)이 왼쪽, y좌표가 큰 (4,7)이 오른쪽으로 갑니다.
오른쪽에는 (8,1),(9,6)이 오는데 점이 두 개밖에 없으니 아무 거나 하나는 위에 두고 하나는 밑에 두면 되요. (9,6)을 위에 두고 y좌표가 작은 (8,1)은 왼쪽에 두면 되겠네요.
그러면 이제 k-d tree를 어떻게 활용하죠? 활용을 안 하면 되요.
여러 개의 점들이 주어질 때, 각각의 점에서 가장 가까운 점을 찾을 때 쓸 수 있습니다!
https://www.acmicpc.net/problem/7890
7890번: 가까운 점 찾기
문제 2차원 평면 상에 N개의 점이 주어진다. 1 ≤ i, j ≤ N에 대해서 dist(i, j) = (xj - xi)2 + (yj - yi)2 라 정의할 때, 각각의 점 i에 대해서, Min(dist(i, j)) (1 ≤ j ≤ N, j ≠ i) 를 출력하라. 입력 입력은 여러 개의 테스트 케이스로 주어진다. 첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 15)가 주어진다. 이후 각각의 테스트 케이스마다, 첫 번째 줄에 N (2 ≤ N ≤ 10
www.acmicpc.net
무려 루비네요... 역시 이상한 자료구조에요.