유니온 파인드 (Union-Find) / 분리 집합 (Disjoint Set)
이 글은 제 개인적인 공부를 위해 작성한 글입니다.
틀린 내용이 있을 수 있고, 피드백은 환영합니다.
개요
유니온 파인드는 이름 그대로 합치기와 찾기라는 두 가지 연산으로 여러 개의 요소들 사이의 관계를 효율적으로 관리하는 자료구조이다.
흔히 서로소 집합 알고리즘이라고도 불린다.
분리 집합 (Disjoint Set) aka 서로소 집합
전체 집합 U에 대해, U의 부분 집합 A, B는 다음 조건을 만족한다.
- A, B는 U의 부분 집합이다. (A ⊆ U, B ⊆ U)
- A와 B는 공통 원소를 가지지 않는다. (A ∩ B = ∅)
- A와 B의 합집합은 U이다. (A ∪ B = U)
핵심 연산
유니온 파인드는 각 원소가 어떤 집합에 속해 있는지 트리 구조로 표현한다.
알고리즘 문제를 풀 때는 std::vector
Find : 특정 원소 x가 속한 집합의 루트 노드를 찾는다. 이를 통해 두 원소가 같은 집합에 있는지 확인할 수 있다.
1
2
3
4
5
6
7
8
9
int Find(int x)
{
if (x != parent[x])
{
return Find(parent[x]);
}
return x;
}
Union : 서로 다른 두 집합을 하나로 합친다. 보통 한쪽 트리의 루트 노드를 다른 쪽 트리의 루트 노드의 자식으로 연결한다.
1
2
3
4
5
6
7
8
9
10
void Union(int x, int y)
{
int root_x = Find(x);
int root_y = Find(y);
if (root_x != root_y)
{
parent[root_x] = root_y;
}
}
Path Compression과 Union By Rank/Size
경로 압축 (Path Compression)
생성되는 노드 간의 관계가 항상 (i, i+1) 형태로 연결된다면 1000번째 노드가 루트 노드에 도달하기 위해서는 999번의 재귀 호출이 필요하다. 이는 상당히 비효율적이니, Find 연산을 수행할 때마다 방문하는 모든 노드들이 직접 루트 노드를 가리키도록 업데이트하는 기법이다. 트리의 높이가 획기적으로 낮아져 다음번 Find 연산이 훨씬 빨라진다.
1 2 3 4 5 6 7 8 9
int Find(int x) { if (x != parent[x]) { parent[x] = Find(parent[x]); } return parent[x]; }
높이/크기에 기반한 합치기 (Union By Rank/Size)
두 집합을 합칠 때, 트리의 높이나 크기에 기반하여 합치는 기법이다. 높이가 더 낮은 트리를 더 높은 트리에 붙이거나, 크기가 더 작은 트리를 더 큰 트리에 붙이는 방식이다. 이렇게 하면 트리가 한쪽으로 치우치는 것을 방지할 수 있다. 아래 코드는 랭크에 기반하였는데, 사이즈로 하고 싶으면 트리가 합쳐질 때마다 rank[root_x] += rank[root_y]; 같은 식으로 바꾸면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Union(int x, int y)
{
int root_x = Find(x):
int root_y = Find(y);
if (root_x != root_y)
{
if (rank[root_x] < rank[root_y])
{
parent[root_x] = root_y;
}
else if (rank[root_x] > rank[root_y])
{
parent[root_y] = root_x;
}
else
{
parent[root_y] = root_x;
rank[root_x]++;
}
}
}
시간 복잡도
- 경로 압축, 랭크/사이즈에 기반한 합치기를 사용하지 않는다면 트리가 한쪽으로 치우친 사향 트리 형태가 될 수 있어 O(n)
- 경로 압축과 랭크에 기반한 합치기를 모두 적용하면 $O(\alpha(N))$이라고 한다.
- $\alpha(x)$는 애커만 함수의 역함수인데 $\alpha(x^{65536})$일 때, 5라서 그냥 상수로 봐도 무관하다고 한다.
- Union 함수는 Find 함수의 시간복잡도에 따라 결정된다.
c.f) 사향 트리: 루트를 제외한 모든 노드가 한쪽에 쏠린 트리
백준 4195번 친구 네트워크
https://www.acmicpc.net/problem/4195
Union By Rank/Size에서 랭크란 트리의 높이를 의미하고, 사이즈는 집합의 크기를 의미한다.
이 문제에선 집합의 크기를 알아야 하기에 Union By Size를 사용해야 한다.
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
#include <iostream>
#include <unordered_map>
std::unordered_map<std::string, std::string> parent;
std::unordered_map<std::string, int> rank;
std::string Find(std::string x)
{
if (x != parent[x])
{
parent[x] = Find(parent[x]);
}
return parent[x];
}
void Union(std::string x, std::string y)
{
x = Find(x);
y = Find(y);
if (x != y)
{
if (rank[x] < rank[y])
{
parent[x] = y;
rank[y] += rank[x];
}
else
{
parent[y] = x;
rank[x] += rank[y];
}
}
}
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int test_case;
std::cin >> test_case;
for (int i = 0; i < test_case; i++)
{
parent.clear();
rank.clear();
int friends;
std::cin >> friends;
for (int j = 0; j < friends; j++)
{
std::string x, y;
std::cin >> x >> y;
if (parent.find(x) == parent.end())
{
parent[x] = x;
rank[x] = 1;
}
if (parent.find(y) == parent.end())
{
parent[y] = y;
rank[y] = 1;
}
Union(x, y);
std::string parent_x = Find(x);
std::cout << rank[parent_x] << "\n";
}
}
return 0;
}
백준 16402번 제국
https://www.acmicpc.net/problem/16402
유니온 파인드와 문자열 파싱을 공부할 수 있는 좋은 문제
경로 압축만 수행하면 된다.
한가지 조심할 점은 같은 집합 내에서 루트가 바뀔 수 있다는 점이다.
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
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
#include <iostream>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
std::unordered_map<std::string, std::string> parent;
std::string Find(std::string x)
{
if (x != parent[x])
{
parent[x] = Find(parent[x]);
}
return parent[x];
}
void Union(std::string x, std::string y, bool bRootIsX)
{
std::string parent_x = Find(x);
std::string parent_y = Find(y);
if (parent_x != parent_y)
{
bRootIsX ? parent[parent_y] = parent_x : parent[parent_x] = parent_y;
}
else
{
if (bRootIsX)
{
parent[parent_y] = x;
parent[x] = x;
}
else
{
parent[parent_x] = y;
parent[y] = y;
}
}
}
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::string prefix = "Kingdom of ";
int n, m;
std::cin >> n >> m;
std::cin.ignore();
for (int i = 0; i < n; i++)
{
std::string s;
getline(std::cin, s);
std::string name = s.substr(prefix.length());
parent[name] = name;
}
for (int i = 0; i < m; i++)
{
std::string s;
getline(std::cin, s);
std::stringstream ss(s);
std::string s_name1, s_name2, result;
std::getline(ss, s_name1, ',');
std::getline(ss, s_name2, ',');
std::getline(ss, result, ',');
std::string name1 = s_name1.substr(prefix.length());
std::string name2 = s_name2.substr(prefix.length());
if (result == "1")
{
Union(name1, name2, true);
}
else if (result == "2")
{
Union(name1, name2, false);
}
}
for (const auto& [fst, snd] : parent)
{
Find(fst);
}
std::set<std::string> answer;
for (const auto& [fst, snd] : parent)
{
answer.insert(Find(fst));
}
std::cout << answer.size() << '\n';
for (const auto& elem : answer)
{
std::cout << prefix << elem << '\n';
}
return 0;
}
참고