Goal
- Union-Find에 대한 이해
- Union-Find 알고리즘을 구현할 수 있다
Union-Find란?
Union-Find란, 서로소 집합(Disjoint-Set)을 표현하는 독특한 자료구조이다.
(Union, Find라는 연산을 포함하기 때문에 Union-Find(합집합 찾기)라는 이름이 붙었다)
*Disjoint Set : 서로소 집합을 다루는 자료구조
Union-Find의 연산
union-find에는 다음과 같은 연산을 제공한다.
- make-set(x) : x를 유일한 원소로 하는 새로운 집합을 만든다. => 초기화
- union(x, y) : x가 속한 셋과 y가 속한 집합을 합친다
- find(x) : x가 속한 집합을 찾는다 (집합을 반환, 또는 집합을 대표하는 대푯값(트리의 루트 등)을 반환)
집합 구현은 비트 벡터, 배열, 연결 리스트를 사용해서 구현될 수 있지만, 가장 효율적인 방법은 트리이다.
하나의 트리를 하나의 집합으로 나타낼 수 있고, 그 트리의 루트 노드는 집합을 나타내는 대푯값이다.
시간복잡도 계산
find : O(h)
- 트리의 부모 노드까지 거슬러 올라가야 하므로 트리 높이에 비례한다.
union : O(1)
- 한쪽 트리가 다른 한쪽 트리의 서브 트리가 되면 되기 때문에 O(1)만큼의 시간 복잡도를 갖는다.
- 하지만, 각각의 트리의 루트 노드를 찾아야 하기 때문에 find연산이 전체 수행시간의 대부분을 차지한다.
Union-Find 사용 예시
- make-set : 초기화. => 모든 노드들이 각각 개별 집합이 되도록 초기화. (자신을 루트로하는 개별적인 트리 형태)
- find(x) : x가 속한 트리(집합)의 루트 노드를 찾는 과정. ex) find(x) == find(y)이면, 두 노드는 같은 집합에 속
- union(x,y) : 두 트리를 합치는(union)과정
- find(x), find(y)를 통해 두 노드가 속한 집합을 구한다.
- find(x) == find(y) 라면 두 노드가 속한 집합이 같으므로 합칠 필요가 없다.
- find(x) != find(y() 라면 두 노드가 속한 집합이 다르므로 합친다. (한쪽 노드의 부모 노드만 변경하면 됨)
위 과정에서 find 연산의 성능은 트리 높이에 영향을 받으므로,
합칠 때, height값이 작은 쪽이 큰 쪽으로 합쳐지면 find 연산을 좀 더 효율적으로 할 수 있다.
Union-Find의 구현
const int MAX_SIZE = 100001;
int parent[MAX_SIZE];
void make_set()
{
for (size_t i = 0; i < MAX_SIZE; i++)
{
parent[i] = i; // 초기화. root노드인 경우 parent를 자기 자신으로 초기화(계산의 편의성을 위해 세팅)
}
}
int find(int x)
{
if (x == parent[x]) // 루트 노드인 경우
{
return x;
}
return find(parent[x]); // 최상위 부모 노드를 찾아서 리턴
}
void unite(int x, int y)
{
// 각 원소가 속한 트리의 루트 노드를 찾는다
x = find(x);
y = find(y);
parent[y] = x; // y가 속한 트리를 x가 속한 트리의 subtree로 합친다.
}
Union-Find를 위와 같이 구현하면 다음 그림과 같은 최악에 상항에서 나쁜 성능을 보일 수 있다.
위와 같은 Skewed Tree의 경우 최악의 상황에서는 find연산이 선형적인 시간복잡도를 갖게된다. (최악의 경우 O(N))
그래서 좀 더 최적화 할 수있는 방법이 필요하다.
Union-Find 연산의 최적화 방법
- 경로 압축(Path Compression) => find 연산시 수행되는 방법
- union-by-height(=union-by-rank) => union 연산시 수행되는 방법
- union-by-size => union 연산시 수행되는 방법
참고)
위 두가지 방법을 동시에 수행하면 경로 압축에 의해 트리의 height값이 변경 될 수 있으므로 union-by-height에서 계산한 height값이 정확한 값이 아닐수도 있다.
경로 압축(Path Comporession)
find연산을 할 때 수행되는 과정으로, 루트 노드와의 경로를 압축하는 과정이다.
find(x)를 하면, x와 루트 노드 경로사이에 존재하는 모든 노드가 자신의 부모 노드로 루트 노드를 가리키게 된다.
다음 그림에서 find(0)을 할 경우, 노드(0)과 루트 노드(5) 사이에 존재하는 노드{0, 2, 3, 4}는 모두 자신의 부모 노드로 루트노드(5)를 가리키게 된다. => 경로 압축. (루트와의 경로 길이가 1로 변경)
경로를 압축하는 find 함수를 코드로 구현하면 다음과 같다.
int find(int x)
{
if (x == parent[x])
{
return x;
}
return parent[x] = find(parent[x]); // 경로 압축 => 자신의 부모 노드로 루트 노드를 가리키게됨
}
시간 복잡도 : O(h)
union-by-height
union 연산을 수행할 때 수행되는 과정으로, 상대적으로 높이가 더 작은 트리가 큰 트리 쪽으로 합쳐지는 방법이다.
합쳐진 트리의 높이는 기존 두 트리의 최대 높이 값과 같거나 1 더크다. (높이가 같은 경우 기존 높이보다 1 커짐)
- 두 트리의 최대 높이가 다른 경우 높이 : max(x,y)
- 두 트리의 최대 높이가 같은 경우 높이 : max(x,y) + 1
코드 구현
void unite(int x, int y)
{
// 각 원소가 속한 트리의 루트 노드를 찾는다
x = find(x);
y = find(y);
if (x == y) // 같은 트리에 있다면 합치지 않는다.
{
return;
}
if (height[x] < height[y])
{
parent[x] = y; // x -> y로 합침
}
else
{
parent[y] = x; //y -> x로 합침
if (height[x] == height[y]) // 높이가 같았을 경우 최대 높이가 1 증가한다.
{
height[x]++;
}
}
}
union-by-height연산을 하면 트리의 높이가 증가되는 값을 줄일 수 있지만, 높이를 저장할 추가공간이 필요하다는 단점이 있다.
union-by-size
union 연산을 수행할 때 수행되는 과정으로, 상대적으로 size가 더 작은 트리가 큰 트리 쪽으로 합쳐지는 방법이다.
*size : 트리 노드의 개수
구현 코드
const int MAX_SIZE = 100001;
int parent[MAX_SIZE];
int nodeCount[MAX_SIZE];
void make_set()
{
for (size_t i = 0; i < MAX_SIZE; i++)
{
parent[i] = i;
nodeCount[i] = 1;
}
}
int find(int x)
{
if (x == parent[x])
{
return x;
}
return parent[x] = find(parent[x]);
}
void unite(int x, int y)
{
x = find(x);
y = find(y);
if (x == y) return;
else if (nodeCount[y] < nodeCount[x])
{
parent[y] = x;
nodeCount[x] += nodeCount[y]; // x의 node 수에 y의 node 수를 더한다.
}
else
{
parent[x] = y;
nodeCount[y] += nodeCount[x]; // y의 node 수에 x의 node 수를 더한다.
}
}
References
gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html
https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/UnionFind.pdf
'알고리즘 > 알고리즘 이론' 카테고리의 다른 글
소수 찾기 (0) | 2020.07.02 |
---|---|
Kruskal 알고리즘 (0) | 2020.07.01 |
그래프 순회(Graph Traversal) - BFS , DFS (0) | 2020.07.01 |
반복과 재귀 (0) | 2020.06.30 |
코딩 테스트 입문 (with C++) (0) | 2020.06.11 |