Subject
Union Find
Implementation
1. Union Find
1) General of Union Find.
union find는 disjoint set이라고도 불리우는 자료구조로 흔히 집합의 포함관계를 표현하는데 사용되며, 대단히 빠른 시간 안에 소속 여부를 판단할 수 있다. 유니온 파인드는 크게 3가지 요소로 구성되는데, 부모를 표현하기 위한 메모리(테이블), 유니온 함수, 파인드 함수가 바록 그것이다.
유니온 파인드 구조 내에서 각 원소들은 hierachical한 트리의 형태로 구성된다. 여기서 일반적인 트리와 다른 점이 있다면, 자식 노드가 부모 노드를 가리킨다는 점이다. 테이블을 통해서 부모의 부모를 거듭해서 찾다 보면 최종적으로 자기 자신을 가리키는, 트리의 root에 도달하게 되는데, 이 루트 노드의 값으로 소속 관계를 식별한다. 여기서 테이블은 각 원소의 부모를 저장하는 역할을 맡는다.
파인드 함수는 테이블을 재귀적으로 참조하며, 최종적으로는 해당 노드가 속한 트리의 루트 노드를 반환한다. 루트 노드는 트리에서 단 하나만 존재한다는 점을 통해서 각 노드가 서로 다른 트리에 속해있는지를 판단할 수 있다.
유니온 함수는 트리에 노드를 추가하는 역할을 한다. 일반적으로 테이블에 자기 자신과 부모를 쌍으로 하는 엔트리를 추가하는 방식으로 구성된다.
union 알고리즘의 시간 복잡도는 테이블에 단순히 등록만 하면 끝이기에 O(1)이라 할 수 있다. 하지만, find 알고리즘의 시간 복잡도는 트리가 어떤 방식으로 구조화 되었느냐에 따라 결정된다. 따라서 최악의 경우는 모든 노드가 트리 내에서 선형으로 연결되는 형태이며, 이 때 find는 O(N)의 시간 복잡도를 갖는다. 즉, 유니온 파인드의 명성에 무색하게 생각보다 부족한 성능을 보이며, 이를 극복하기 위해서 다음의 구조가 등장했다.
2) Union by rank.
앞서 find 알고리즘의 성능이 트리의 모양, 깊이에 따라서 결정됨을 알았다. 이를 해결하기 위해서 등장한 방법이 바로 union by rank이다. 이 방식은 트리의 깊이가 증가하는 것을 방지하고자 고안되었다. 먼저 트리를 대표하는 루트 노드에게 해당 트리의 깊이를 음수값으로 저장한다. 음수값으로 저장하는 이유는 스스로가 루트 노드임을 구분하기 위해서이다.
유니온 과정에서 트리의 깊이가 증가하는 것은 상대적으로 짧은 트리에 긴 트리를 붙이기 때문이다. 만약 긴 트리에 짧은 트리를 붙인다면, 길이의 증가량이 없거나, 있더라도 그 증가량이 상대적으로 다를 것이다. 따라서 union과정에서 루트 노드가 저장하는 rank(트리의 깊이)를 확인하고, 이를 바탕으로 깊은 트리에 얕은 트리를 붙이도록 유도하여 트리의 깊이가 증가하는 것을 방지한다.
3) Path Compression.
경로 압축은 보다 직접적으로 트리의 깊이를 줄이는 방법이다. 간단하게 말하면, find의 대상이 되는 노드와 그 조상 전부를 루트의 자식 노드로 입양시키는 것이다.
find를 수행하는 과정에서는 필연적으로 트리를 거슬러 오르며 root의 값을 찾는 과정이 수반된다. 여기에 재귀를 이용하면 최초의 탐색 대상과, 그 부모들은 모두 자신의 root가 어떤 값인지를 알게 된다. 따라서 우리는 탐색 과정에서 만나는 모든 조상 노드의 부모를 root로 초기화 할 수 있다.
Union by rank를 통해서 트리를 균형된 형태로 발전시킬 수 있으며, Path Compression을 통해서 한 번 탐색한 노드에 대해서는 탐색 시간을 극단적으로 줄일 수 있다. 따라서 최악의 경우 O(log N), 최선의 경우 O(1)을 달성할 수 있다.
2. Implementation
1) example in C/C++
앞서 살펴본 유니온 파인드 알고리즘을 코드로 나타내면 다음과 같다.
int parent[MAX_NODE_NUM] // 랭크와 root노드를 기록하기 위한 메모리
int find(int target_index)
{
if (parent[target_index] < 0) // 0보다 작다 -> 랭크값, 즉 루트
{
return target_index; // 자기 자신을 반환함.
}
else // 루트에 오르기 전까지 계속 재귀적으로 찾아나감
{
// path compression
int p = find(parent[target_index]); // 재귀의 결과 얻어진 p는 루트
parent[target_index] = p; // 자신을 루트에 입양, 실제 depth 감소 but rank수정이 없음
return p;
}
}
void Union( int node1, int node2)
{
node1 = find(node1);
node2 = find(node2); // find 과정에서 path compression후 루트 획득
if (node1 == node2) // 이미 같은 set, do nothing
{
return;
}
// union by rank
if (parent[node1] < parent[node2]) // 랭크(절대값)가 큰 쪽이 부모가 된다.
{
// node1의 랭크 값이 더 크다, 고로 node1이 부모가 된다
// 하지만 해당 구현에서는 경로 압축으로 인한 랭크의 변화가 없다.
parent[node1] += parent[node2]; // 랭크 값의 절댓값 증가(음수임)
parent[node2] = node1; // 루트를 갱신
}
else
{
parent[node2] += parent[node1];
parent[node1] = node2;
}
}
C++
복사
위의 코드는 PS 과정에서 사용하기 위한 union find 구현이다. 해당 구현에서는 경로 압축의 경우는 제대로 구현되어 있지만, union by rank는 불완전하다. 그 이유는 path compression에 의한 트리의 rank 감소가 반영되지 않기 때문이다.
2) example in PS - BOJ1939
이하는 앞서 살펴본 유니온 파인드를 응용한 실제 문제풀이 사례이다. 해당 문제는 크게 2가지 풀이 방법이 존재하는데, 하나는 weight에 대한 이진 parametric search를 수행하는 것이고, 다른 하나는 크루스칼 알고리즘을 사용하는 것이다. 이하는 유니온 파인드를 응용한 최소 신장 트리 알고리즘인 크루스칼 알고리즘으로 풀이했다.
//BOJ1939, 중량 제한
//kruskal algorithm
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <tuple>
#include <vector>
typedef std::tuple<int, int, int> edge;
int N, M, ans, start, end;
int parent[10001];
edge edges[100001];
int find(int target_index);
void Union(int node1, int node2);
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
memset(edges, 0, sizeof(edges));
memset(parent, -1, sizeof(parent));
// input, 노드의 수와 에지의 수
std::cin >> N >> M;
for (int i = 1; i <= M; ++i)
{
std::cin >> std::get<0>(edges[i]) // a, 노드 번호
>> std::get<1>(edges[i]) // b, 노드 번호
>> std::get<2>(edges[i]); // c, 가중치(중량)
}
std::cin >> start >> end; // 시종점
// 정렬을 위한 람다함수
auto comp = [](const edge& e1, const edge& e2) -> bool
{
return std::get<2>(e1) > std::get<2>(e2);
}; // 가중치 기준으로 에지의 내림차순 정렬
std::sort(edges, edges + M + 1, comp);
// 크루스칼 알고리즘.
int pos = 0; // 에지의 인덱스
while (find(start) != find(end)) // 최소 신장 트리로 종점에 도착하는지
{
int node1 = std::get<0>(edges[pos]);
int node2 = std::get<1>(edges[pos]);
if (find(node1) != find(node2)) // find의 결과가 서로 다르다 -> 미신장 노드
{
ans = std::get<2>(edges[pos]); // 정렬의 결과 갈수록 가중치 감소함
Union(node1, node2); // 트리의 신장
}
pos++;
}
std::cout << ans;
}
int find(int target_index)
{
if (parent[target_index] < 0)
{
return target_index;
}
else
{
// path compression
int p = find(parent[target_index]);
parent[target_index] = p;
return p;
}
}
void Union( int node1, int node2)
{
node1 = find(node1);
node2 = find(node2);
if (node1 == node2)
{
return;
}
// union by rank
if (parent[node1] < parent[node2]) // 랭크(절대값)가 큰 쪽이 부모가 된다.
{
// node1의 랭크 값이 더 크다, 고로 node1이 부모가 된다
parent[node1] += parent[node2]; // 랭크 값의 절댓값 증가(음수임)
parent[node2] = node1; // 루트를 갱신
}
else
{
parent[node2] += parent[node1];
parent[node1] = node2;
}
}
C++
복사
크루스칼 알고리즘은 최소 신장트리를 구하는 알고리즘의 일종으로, 유니온 파인드를 이용해서 구현된다. 크루스칼 알고리즘을 간략하게 설명하면 다음과 같다.
1.
가중치를 기준으로 에지를 정렬한다.
2.
정렬된 에지들을 순서대로 순회하면서 에지를 이루는 양 노드에 대해서 파인드를 수행한다.
a.
수행한 결과, 한 에지의 두 노드가 서로 같은 set이다. → 이미 트리의 일부분, continue.
b.
수행한 결과, 서로 다른 set이다.→ 서로 다른 트리의 일부, union
3.
최소 신장 트리는 루프가 없으므로, (union한 edge의 수)가 (노드의 수 - 1)이 되면 종료한다.
해당 문제의 경우, union by rank와 path compression을 적용하지 않으면 시간 복잡도를 극복할 수 없다.
