[Algorithm] 서로소 집합(Disjoint Set)
👻 Disjoint Set
서로소 집합 혹은 상호 배타적 집합이라고도 불리는 Disjoint Set은 서로 배타적인 집합으로써 공통된 원소를 가지고 있지 않는 집합을 의미한다. 유니온-파인드(Union-Find) 기법을 사용하며 직역하면 합치기-찾기라는 뜻이고 말 그대로 트리 구조에서 합치고 찾는 과정을 통해 데이터에 접근하는 방식이다. 이 자료 구조는 최소 스패닝 트리(Minimum Spanning Tree)를 만드는 데 사용된다.
🌱 초기화
서로소 집합의 초기화는 노드의 개수만큼 부모 노드를 담는 배열 _parent를 생성한다. 집합을 생성할 때에는 부모 노드가 연결되어 있지 않으므로 자기 자신을 가리킨다. 그리고 모든 노드는 연결되어 있지 않는 상태로 생성이 된다.
🌱 Find
서로소 집합 구조에서 원하는 노드를 찾는 Find 연산이다. 여기서 원하는 노드는 해당 노드의 가장 위에 있는 노드, 즉 나를 가지고 있는 루트 노드를 찾아서 반환해준다. 깊이가 깊은 노드라도 재귀적으로 함수를 호출하여 부모의 부모 노드를 찾아 타고 올라가는 방식으로 루트 노드를 찾는다.
int Find(int u)
{
if (u == _parent[u])
return u;
return Find(_parent[u]);
}
🌱 Union
서로 공통적인 요소를 가지고 있지 않는 트리 구조의 데이터들을 하나로 합쳐주는 Union 연산이다. 두 개의 노드를 합치게 되면 그 즉시 연산이 이루어진다.
// u와 v를 병합 (u가 v 산하로)
void Merge(int u, int v)
{
u = Find(u);
v = Find(v);
if (u == v)
return;
_parent[u] = v;
}
하지만 여기서 문제가 발생할 수 있다. 단 한 번도 루트 노드나 부모 노드와 병합하지 않고 리프 노드에만 병합을 시도하게 된다면 연결 리스트와 같은 구조의 트리 모양이 생성될 것이다. 그렇게 되면 시간 복잡도는 최악의 경우 O(N)을 가지게 된다.
👻 최적화
위에서 본 문제를 해결하기 위한 방법이 존재한다. 바로 경로 압축(Path Compression)과 유니온 바이 랭크(Union By Rank)라는 두 가지 방법이다.
🌱 경로 압축
경로 압축(Path Compression)은 말 그대로 트리의 높이를 줄여 원하는 노드까지 도달하는 경로를 단축시켜주는 방법이다. Find 연산에서 재귀적으로 함수를 호출할 때마다 해당 노드의 부모 노드를 설정해주면 연결 리스트처럼 생성된 선형 트리의 구조에서 자식, 자손 노드들은 모두 루트 노드로 붙게되며 경로가 줄어들게 될 것이다.
int Find(int u)
{
if (u == _parent[u])
return u;
return _parent[u] = Find(_parent[u]);
}
return 부분의 코드에서 부모 노드의 값을 바꿔주면 쉽게 트리를 최적화할 수 있다.
🌱 유니온 바이 랭크
유니온 바이 랭크(Union By Rank)는 Union 연산 시 사용되는 방법이며 말 그대로 합칠 때마다 랭크(순위)를 부여하여 비교해서 더 나은 방향으로 트리를 합치도록 방향을 제시해주는 방법이다. 보통 랭크로는 트리의 사이즈(Size) 혹은 높이(Height)를 설정해줄 수 있는데, 여기서는 랭크를 높이로 설정하여 최적화하는 방법에 대해 알아보자.
void Merge(int u, int v)
{
u = Find(u);
v = Find(v);
if (u == v)
return;
if (_rank[u] > _rank[v])
swap(u, v);
// rank[u] <= rank[v] 보장됨
_parent[u] = v;
if (_rank[u] == _rank[v])
_rank[v]++;
}
우선 합쳐질 두 노드의 루트 노드를 찾아주는 Find 연산을 통해 각각의 트리 구조에서 경로 압축이 실행되고 u와 v는 루트 노드로 변경될 것이다. 두 값이 일치하면 동일한 루트 노드를 가지는 노드들이므로 바로 종료되고, 그렇지 않은 경우 랭크(높이)를 비교하여 나머지 작업을 수행한다.
랭크를 트리의 높이로 잡고 Union 연산 시 u가 v의 산하로 들어간다는 조건뿐 아니라 무조건 높이가 낮은 트리를 트리의 높이가 높은 트리 밑에 추가한다는 조건이 있다. 이 조건을 지키기 위해 랭크(높이)를 비교하고, 산하로 들어갈 u 노드의 트리가 v 노드의 트리보다 높다면 서로 값을 교환해주는 예외 처리를 한 번 해주었다.
그런 다음 u의 부모 노드를 v로 변경해주고, 만약 두 트리의 높이가 동일하다면 한 트리가 산하로 들어가면서 높이가 1 증가하게 되니 랭크의 값도 1 증가시켜줘야한다.
이렇게 트리의 최적화를 해주게 되면 최악의 상황인 O(N)의 시간 복잡도가 나오지 않고 트리는 계속 재구성되며 그리 높지 않은 구조를 유지하게 될 것이다. 이러한 과정을 거쳐 평평한 트리가 완성되면 Find 연산은 O(1)의 시간 복잡도를 갖게 될 것이다.
💡 정확하게 말하자면 Find 연산은 호출할 때마다 수행 시간이 변한다(트리의 경로 압축, 재구성 때문). 따라서 Find 연산의 실제 시간 복잡도는
O(Ackermann(N))이라고 한다.아커만 함수(Ackermann Function)로 도출된 값은 상수와 동일하다.
계속 읽어봐도 무슨 말인지 잘 모르겠는데..😕
👻 글을 마치며
이번 시간에는 서로소 집합에 대해 알아보았다. 개념이 생소하고 최적화 방법에 헷갈리는 부분이 많았지만 부모 노드의 정보 하나만을 갖고 있어 직관적이고 굉장히 편리한 방법이라는 생각이 들었다. 다만 조금 더 깊게 들어가면 이해하지 못하는 부분이 발생하게 되는데 예전만큼은 아니지만 그래도 대충 훑고 넘어가려는 이 마인드를 조금이라도 더 줄여봐야겠다. 그래도 많이 나아진거지만.. 😅
Leave a comment