9 min to read
명예 STL - Union find 구현하기
상호 배타적 집합을 어떻게 구현할 수 있을까?
개요
C++의 STL은 꽤나 많은 자료구조와 알고리즘들을 구현해 놓았다. std::list라던가, std::stack 등등…. 하지만, 내장되어 있지 않은 자료구조와 알고리즘도 상당히 많다는 사실을 부정할 수는 없기 때문에, 블로그 포스팅을 통해서, 반드시 알아둬야 할 문제풀이에 상당히 유용히 쓰이는 알고리즘들을 명예 STL 이라고 내 맘대로 이름 붙여서 이제 관리해볼려고 한다.
Union Find가 필요한 이유
상호 배타적 집합(disjoint set)을 표현하는데에 쓰는 자료구조 입니다. 상호 배타적 집합이라는 이름에서 추측할 수 있듯이, 상호 배타적 집합은, 서로 공통원소가 없는 집합을 의미합니다.
종만책으로 잘 알려진 프로그래밍 대회에서 배우는 알고리즘 전략이라는 책에서 소개하는 이야기를 소개해볼까 합니다.
어떤 파티에 \(n\)명의 사람이 왔다고 합시다. 레크레이션 강사가 생일이 같은 사람들끼리 뭉치라고 했을 때, 처음에는 모두 혼자 돌아다니다, 생일이 같은 사람을 찾게 되면 그 사람들 끼리는 팀을 이루어 함께 움직이게 됩니다. 다른 팀을 만났을 때, 생일이 같다는것을 알게 되면 두 팀은 뭉쳐서 한 팀을 구성하는 식으로 움직이게 되겠지요.
파티에 온 사람들의 전체 집합으로 놓고 보면, 팀은 이 집합을 여러개의 부분집합으로 쪼갠것 입니다. 각 팀은 생일이 같은 사람들로 구성되었기 때문에, 두 개 이상의 팀에 속한 사람은 없다는 점에 유의합시다. 이렇게 공통 원소가 없는, 다시말해 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조가 바로 유니온-파인드 구조입니다.
이러한 것들을 컴퓨터 언어에서 다룰 수 있게 해주는 유니온-파인드 구조가 할 수 있어야 하는 연산은 다음과 같습니다.
- 초기화 : n개의 원소가 각각의 집합에 포함되어 있도록 초기화
- 합치기(union) 연산 : 두 원소 a,b가 주어질 때, 이들이 속한 두 집합을 하나로 합침
- 찾기(find) 연산 : 어떤 원소 a가 주어질 때 이 원소가 속한 집합을 반환
초기화 연산은 처음 구조를 만들때 외에는 그렇게 자주 쓰지 않으니, 상대적으로 자주 쓰는 두 연산의 이름을 따서 union-find 자료구조라고 합니다.
구현
이제 대략적인 union-find 자료구조의 개념과 필요성을 알았습니다. 이제 어떻게 실제 코드상에서 이를 구현할 수 있는지 알아봅시다.
배열로 구현하기
union-find 자료구조를 구현하는 가장 간단한 방법은 1차원 배열 하나를 이용해서 아래와 같이 만드는 것입니다.
belongsTo[i] = i번 원소가 속하는 집합의 번호
처음에는 belongsTo[i] = i로 두면, 찾기 연산을 상수 시간안에 할 수 있게 됩니다.
하지만 이 방법의 문제는 합치기 연산입니다. 합치기 연산을 위해서는 belongsTo[]의 모든 원소를 순회하면서 한쪽 집합에 속한 원소들을 다른쪽 원소의 집합으로 옮겨야 하는데, 모든 원소를 순회하는데에는 \(O(N)\)의 시간이 걸립니다. 찾기 연산이 \(O(1)\)이라는 사실은 매우 좋으나, 합치기 연산의 비용이 크기 때문에 다른 방법을 고안해볼 필요가 있습니다.
트리를 이용해 표현하기
배열표현의 “합치기 연산이 느리다”라는 단점을 극복하는 좋은 방법 중 하나는, 트리를 이용해서 이를 구현해보는 것입니다. 이 표현에서는 한 집합에 속하는 원소들을 하나의 트리로 표현하여, 상호 배타적 집합이 트리들의 집합이 되도록 합니다. 아래의 그림 1에서 여덟개의 원소가 두개의 집합으로 분할되어 있는것을 볼 수 있습니다.
이런 표현을 사용할 때, 두 원소가 같은 트리에 속해있는지 확인하는 방법(즉 find 연산을 구현하는 방법)은 원소가 속해있는 트리의 루트가 같은지를 비교하는 것입니다. 트리와 루트는 항상 1:1 대응되므로(루트가 2개 이상 있는 트리는 존재하지 않으니까) 루트가 같다면 두 원소가 같은 트리에 있음을 자명하게 알 수 있습니다. 따라서 이 방법에서의 찾기 연산은 주어진 원소가 포함된 트리의 루트를 찾는 것으로 구현할 수 있습니다.
위의 연산을 구현하기 위해서 자식 노드들이 부모 노드의 정보를 알고 있어야 합니다. 하지만, 부모 노드는 자식 노드에게 갈 일이 없기 때문에 자식 노드에 대한 정보를 저장할 필요가 없지요. 또, 루트는 그 부모가 없으므로, 자기 자신을 부모로 지정합니다.
합치기 연산은 어떻게 구현 될까요? a와 b노드를 하나의 집합으로 합쳐야 한다고 합시다. 각 노드의 루트를 찾은 다음, 한 트리의 루트를 다른 트리의 루트의 자식으로 만들면 됩니다.
이와 같은 자료구조의 구현을 아래 코드에서 볼 수 있습니다.
struct NaiveDisjointSet{
vector<int> parent;
NaiveDisjointSet(int n) : parent(n){
for(int i = 0; i < n; ++i)
parent[i] = i;//초기화
}
//u가 속한 트리의 번호를 반환
int find(int u) const {
if(u == parent[u]) return u;//u가 루트인 경우
return find(parent[u]);
}
//u가 속한 트리와 v가 속한 트리를 합친다
void merge(int u, int v){//union이 C/C++ 예약어라서 다른 단어로 대체
u = find(u); v = find(v);
//이미 u와 v가 같은 트리인 경우를 걸러낸다
if(u == v) return;
parent[u] = v;
}
}
여기서 find()의 시간 복잡도는 대상이 되는 트리의 높이에 비례하는 시간이 걸립니다. merge()함수의 시간복잡도 또한 find가 지배하기 때문에, 이 역시 트리의 높이에 비례하겠군요.
트리 구현의 최적화
이와 같은 트리의 표현을 이용하면 합치기 연산을 할 때, 집합에 포함되는 모든 원소를 변경하는 대신, 루트 하나의 정보만 변경하면 된다는 장점이 있습니다. 하지만, 위에서 언급했듯, 이 방법의 시간 복잡도는 트리의 높이에 의해서 결정되고, 트리가 한쪽으로 기울어 진다면 어떻게 될까요? 최악의 상황을 가정해 보면, 트리가 한쪽으로만 기울어져서 연결 리스트와 같은 형태가 된다면, 시간 복잡도는 \(O(N)\)이 되어, 기존 배열 방식보다도 좋지 않게 됩니다.
이러한 문제를 해결하기 위해 여러가지 방법들이 고안되어 있습니다. 그 중 간단한 것은 두 트리를 합칠 때, 항상 높이가 더 낮은 트리를 더 높은 트리 밑에 집어넣음으로써 트리의 높이가 높아지는 상황을 방지하는 것입니다. 이러한 최적화를 랭크에 의한 합치기(union-by-rank)라고 합니다. 여기서 높이라는 말을 쓰지 않고 랭크라는 말을 쓴 이유는, 밑에서 추가로 설명할 경로 압축 최적화 등 다른 방법을 적용한다면 높이와 다를 수 있기 때문입니다.
아래의 코드는 이와 같은 최적화를 구현한 merge()함수를 보여줍니다.
struct OptimizedDisJointSet {
vector<int> parent, rank;
OptimizedDisjointSet (int n) : parent(n), rank(n,1){
for(int i = 0; i < n; ++i)
parent[i] = i;
}
int find(int u){
if(u == parent[u]) return u;
return parent[u] = find(parent[u]);
}
void merge(int u ,int v){
u = find(u); v = find(v);
if(u == v) return;
if(rank[u] > rank[v]) swap(u,v);
//이제 v의 랭크가 u의 랭크보다 낮지 않으므로 u를 v의 자식으로 보낸다
parent[u] = v;
if(rank[i] == rank[v]) ++rank[v];
}
};
간단한 코드 한줄을 추가한것 뿐이지만, 이 방법으로도 find()함수를 실행하는데 걸리는 시간을 크게 절약할 수 있습니다. 트리의 높이가 증가하기 위해서는 합쳐진 두 트리의 높이가 같을 때만 증가하므로, 높이가 \(h\)인 트리가 생기기 위해서는 높이가 \(h-1\) 개인 두개의 트리가 합쳐져야 하고, 높이가 \(h-1\)이 되기 위해서 \(x\)개의 노드가 필요하다 하면, 높이가 \(h\)되기 위해서는 \(2x\)만큼의 노드가 필요 합니다. 따라서, 트리의 높이는 포함한 노드의 로그에 비례하며, 합치기, 찾기 연산의 시간 복잡도는 \(O(lgN)\)이 됩니다.
경로 압축 최적화
사실 여기서 더 최적화를 진행할 수 있습니다. 이 방법 또한 그렇게 복잡하지는 않은데요, 연산들을 하다가 보면, 찾기 연산이 중복된 계산을 여러번 하고 있음을 느낄 수 있을 것입니다. 이에 착안해서, find(u)를 통해서, 찾아낸 u가 속한 트리의 루트를 parent[u]에 반영한다면, 다음에 find(u)가 호출되었을 때, 경로를 찾아갈 필요 없이 빠르게 루트를 찾을 수 있겠지요. 이런 최적화를 경로 압축(path compression)최적화라고 합니다. 코드 2의 find함수에는 아까 설명한 최적화가 반영이 되어 있습니다. return parent[u] = find(parent[u]);라는 코드가, 재귀적인 구현 덕분에 u부터 루트까지 올라가는 경로 상에 있는 모든 노드들에게 적용이 됩니다.
두가지 최적화를 모두 적용한 연산시간은 분석하기에 매우 까다롭습니다. find()연산은 호출할 때마다 수행 시간이 바뀌기 때문에 분할 상환 분석을 이용해하 하고요. 찾기와 합치기 연산을 아주 여러번 수행했을 때 각 수행에 걸리는 평균 시간은 \(O(\alpha (n))\)이라고 합니다. \(\alpha (n)\)은 애커만 함수를 이용해서 정의되는 함수로, 자세한 것은 여기서 다루지 않지만, 중요한것은 우리가 상상할 수 있는 모든 크기의 \(n\)에 대해서 4 이하의 값이라고 합니다. \(\alpha (n) = 5\)가 되는 첫번째 n은 약 \(2^{2^{2^{65546}}}\) 정도라고 합니다. 따라서 현실적인 모든 입력에 대해서 상수시간에 동작한다고 봐도 되겠지요.
랭크에 의한 최적화가 경로 압축 최적화를 해도 최적이 될까?
맨 처음에 책에서 이와 관련된 내용을 봤을 때 든 질문이었습니다. 일단 제가 내린 결론은 “그렇다” 이고, 이유로 느낀 것도 상당히 간단했습니다. 랭크라는 것은 가능한 높이의 상한선이고, 설사 “높이”가 낮은 트리 위에 “높이”가 높은 트리가 자식으로 들어간다 해서, 트리의 “높이”가 높아진다고 해도, find()를 하면서 다시 트리의 높이를 낮추어 가니까 상관이 없다…라고 생각이 들었다. 만약에 올바른 개념을 알고 계신 분이 있다면 댓글로 관련한 설명을 첨부해 주시길 바랍니다.
마무리하며
union-find가 할 수 있는 연산은 그래프 자료구조도 할 수 있지만, 구현이 간단하고 시간복잡도가 우수해서, 다른 알고리즘의 일부분으로도 쓰이는 꼭 알아둬야 할 자료구조라고 생각됩니다.
union-find를 이용해서 연결성을 확인하는 문제나, 다른 정보들을 추가해서 집합의 크기를 추적한다거나 하는 응용도 할 수 있습니다. union-find를 쓰기 좋은 문제는 백준 1043번 거짓말 문제가 있습니다. 이 문제 상황에서, 같은 파티에 있는 사람들을 하나의 집합으로 묶고, 가능한 파티의 개수를 셀 때, 파티에 속한 사람이 진실을 아는 사람과 같은 집합에 있는지를 체크하는 식으로 문제를 풀어나갈 수 있을 것입니다.
이 포스팅은 구종만씨의 “프로그래밍 대회에서 배우는 알고리즘 문제 해결”을 참조하여 작성하였습니다.
