상호 배타적 집합 (Disjoint Set) : 유니온-파인드 (Union-Find)

상호 배타적 집합

• 공통 원소가 없는, 즉 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조가 바로 유니온-파인드 자료 구조이다.

Example

• 어떤 파티에 n명의 사람들이 왔다고 하자.
• 생일이 동일한 사람들끼리 팀을 구성할 때, 같은 사람을 한 번 찾게 되면 이 사람들은 팀을 이뤄 같이 움직인다.
• 그리고 다른 팀과 생일이 같다는 것을 확인하면 곧장 두 팀은 합쳐지게 된다.

상황 표현 및 연산

• 우선 각 사람을 0 ~ n - 1 까지의 원소로 표현한 뒤, 각 1개의 원소를 포함하는 n개의 집합을 만든다.
• 두 사람 a와 b가 서로 생일이 같다는 사실을 알 때마다 두 사람이 포함된 집합을 합치게 된다.
• 이와 같은 일들을 구현하기 위해 세 가지 연산이 필요하다.
  • 초기화 : n개의 원소가 각각의 집합에 포함되어 있도록 초기화한다.
  • 합치기 (Union) 연산 : 두 원소 a, b가 주어질 때 이들이 속한 두 집합을 하나로 합친다.
  • 찾기 (Find) 연산 : 어떤 원소 a가 주어질 때 이 원소가 속한 집합을 반환한다.

 

배열로 상호 배타적 집합 표현하기

• 가장 간단하게 표현할 수 있는 방법은 1차원 배열 하나를 이용하는 것이다.

belongsTo [i ] = i 번 원소가 속하는 집합의 번호

• 처음에 belongsTo 를 각자 다른 숫자 (belongsTo [i ] = i 로 두면 될 것이다.) 로 초기화하면 크기가 1인 n 개의 집합을 쉽게 만들 수 있다. 
• 이렇게 할 경우 찾기 연산을 상수 시간에 구현할 수 있다.

문제점 : 합치기 연산

• 이 연산을 수행하기 위해서는 belongsTo [] 의 모든 원소를 순회하면서 한쪽 집합에 속한 원소들을 다른 쪽 집합으로 옮겨 주어야 하는데, belongsTo [] 의 모든 원소를 순회하는 데는 O (n ) 의 시간이 걸린다.

 

트리를 이용한 상호 배타적 집합의 표현

• 한 집합에 속하는 원소들을 하나의 트리로 묶어 주기 때문에 트리들의 집합으로 표현된다.
• 아래 그림 (a) 는 원소가 여덟 개인 상호 배타적 집합의 예를 보여주며, 이 원소들이 두 집합으로 분할되어 있는 것을 볼 수 있다.

찾기 연산

• 이 때 두 원소가 같은 트리에 속해 있는지 확인하는 가장 직관적인 방법은 각 원소가 포함된 트리의 루트를 찾은 뒤 이들이 같은지 비교하는 것이다.
• 트리와 루트는 항상 1 : 1 대응되기 때문에, 루트가 같다면 두 노드가 같은 트리에 속해 있다는 것이다.
• 따라서 트리의 루트에 있는 원소를 각 집합의 대표라 해보자.
  • 그림 (a) 에서 3이 속하는 집합의 대표는 5, 2가 속하는 대표는 2이다.
  • 따라서 이 트리에서 찾기 연산은 주어진 원소가 포함된 트리의 루트를 찾는 것으로 구현된다.
• 이런 찾기 연산을 구현하기 위해서는 모든 자식 노드가 부모에 대한 포인터를 가지고 있어야 하는 반면, 부모에서 자식으로 내려갈 필요는 없기 때문에 부모는 자식에 대한 포인터를 가지고 있을 필요가 없다.
  • 그림 (a) 의 모든 화살표가 자식에서 부모로 연결되는 이유이다.
• 루트는 부모가 없으므로 보통 자기 자신을 가리키도록 구현한다.

합치기 연산

• 각 트리의 루트를 찾은 뒤, 하나를 다른 한쪽의 자손으로 넣으면 된다.
• 위 그림의 (b) 는 그림 (a) 에서 1이 포함되는 집합과 4가 포함되는 집합을 합친 결과를 보여준다.
• 한 노드를 다른 노드의 자식으로 넣기 전에 먼저 양 트리의 루트를 찾아야 한다는 점을 기억하자.
  • 이 과정을 생략하면 위 그림 (c) 와 같은 트리가 생긴다.
  • 두 집합이 합쳐진 것이 아니라 1만 다른 집합으로 옮겨가는 것이다.

 

상호 배타적 집합의 최적화

• 트리의 표현을 이용하면 합치기 연산을 수행할 때 루트 하나의 정보만 바꾸면 된다.
• 하지만 연산의 순서에 따라 잘못하면 트리가 한쪽으로 기울어지는 문제가 발생할 수 있다.
  • 예를 들어 두 트리 a, b를 합칠 때, a의 루트를 항상 b의 루트 자식으로 넣는다고 하자.
  • 그러면 0과 1을 합치고, 1과 2를 합치고, ..., 이 과정을 반복하면 높이 n - 1인 트리 (연결리스트) 가 생성된다.
  • 트리의 높이가 O(n)이 되면 합치기 연산, 찾기 연산 모두 O(n)이 되어 버리며, 배열로 구현하는 것보다 효율이 더 나빠진다.

해결 방법

• 쉽게 생각할 수 있는 방법은 두 트리를 합칠 때 항상 높이가 더 낮은 트리를 더 높은 트리 밑에 집어넣음으로써 트리의 높이가 높아지는 상황을 방지하는 것이다.
  • 그림 (a) 에 보이는 두 개의 트리를 (b) 와 같이 합치면 전체 트리의 높이는 여전히 2임을 알 수 있다.
  • 반면 5를 2의 자식 노드로 넣었다면 전체 트리의 높이는 3으로 높아질 것이다.
  • 이 최적화를 랭크에 의한 합치기 (Union-by-rank) 최적화라고 부른다.

코드 구현

• 아래 코드의 Union() 함수는 이와 같은 최적화를 구현한다.
• rank [] 는 해당 노드가 한 트리의 루트인 경우 해당 트리의 높이를 저장한다.
• 두 노드를 합칠 때 높이를 비교해서 낮은 쪽을 높은 트리의 서브트리로 포함하되, 두 트리의 높이가 같은 경우에만 결과 트리의 높이를 1 늘려 주는 것을 볼 수 있다.
• 간단해 보이지만 이 최적화만으로도 Find() 연산에 드는 시간을 크게 줄일 수 있다.
• 이 최적화를 사용하면 트리의 높이는 합쳐진 두 트리의 높이가 같을 때만 증가하므로, 높이가 h인 트리가 생기기 위해서는 높이가 h-1인 두 개의 트리가 합쳐져야 한다.
• 트리의 높이가 h-1이기 위해 최소 x개의 노드가 필요하다면, 높이가 h가 되기 위해서는 최소 2x개의 노드가 필요하다.
• 따라서 트리의 높이는 포함한 노드의 수에 로그에 비례하며, 합치기 연산과 찾기 연산의 시간 복잡도는 O(N)이 아닌 O(lgN)이 된다.

static int[] parent, rank;
static int n;
 
public static void Initialize() {
    for (int i = 0; i < n; i++)
        parent[i] = i;
}
 
public static void Swap(int n1, int n2) {
    int temp = n1;
    n1 = n2;
    n2 = temp;
}
 
public static int Find(int u) {
    if (parent[u] == u)
        return u;
 
    return parent[u] = Find(parent[u]);
}
 
public static void Union(int u, int v) {
    int uR = Find(u);
    int vR = Find(v);
 
    if (uR == vR)
        return;
 
    if (rank[uR] > rank[vR])
       Swap(uR, vR);
 
    parent[uR] = vR;
 
    if (rank[uR] == rank[vR])
        rank[vR]++;
}

• 찾기 연산이 중복된 계산을 여러 번 하고 있다는 데 착안한다.
  • Find(u) 를 통해 u가 속하는 트리의 루트를 찾아냈다고 해보자.
  • 이때 parent[u] 를 찾아낸 루트로 아예 바꿔 버리면 다음번에 Find(u) 가 호출되었을 때는 경로를 따라 올라갈 것 없이 바로 루트를 찾을 수 있을 것이다.
  • 이런 최적화를 경로 압축 (Path Compression) 최적화라고 부른다.
• 위 코드의 Find() 는 경로 압축 최적화의 구현을 보여주며, Find() 를 재귀적으로 구현했다는 점을 눈여겨보자.
• 재귀적인 구현 덕분에 Find(u) 를 호출하면 u에서 루트까지 올라가는 경로 상에 있는 모든 노드들에도 경로 압축 최적화가 자동으로 수행된다.

• 위 그림의 (b) 는 그림 (a) 트리에서 Find(0) 을 수행한 결과를 보여준다.
• 0에서 루트까지 올라가는 경로에 있던 다른 노드 2, 3도 루트에 직접 연결되어 있음을 볼 수 있다.

예제 : 그래프의 연결성 확인하기

• N 개의 도시가 도로망으로 연결되어 있는데, 각 도로는 정확히 두 개의 도시를 연결한다.
• 그런데 이들이 폭설로 인해 모두 마비되었다고 하자.
• 시간이 지남에 따라 하나하나 도로들이 복구되는데, 도로가 복구될 때마다 임의의 두 도시 간에 서로 왕래가 가능한지를 알고 싶다고 하자.

풀이 요약

• 이 문제는 상호 배타적 집합으로 풀 수 있는 전형적인 문제이다.
• 각 도시를 원소로 하고, 서로 왕래가 가능한 도시들을 하나의 집합으로 표시한다.
• 두 도시 a, b를 연결하는 도로가 복구되었으면 원래 a에 연결되어 있던 도시들과 b에 연결되어 있던 도시들 또한 이 도로를 통해 왕래가 가능하다.
• 따라서 두 집합을 합치면 된다.
• 크루스칼의 최소 스패닝 트리 알고리즘이 상호 배타적 집합을 이용해 이와 같은 문제를 해결하는 대표적 사례이다.

예제 : 가장 큰 집합 추적하기

• 상호 배타적 집합은 단순히 두 원소가 같은 집합에 속해 있는지를 확인하는 것 외에도 다른 일들을 할 수 있다.
• 예를 들면 각 집합에 속한 원소의 수를 추적할 수 있다.
• rank[] 처럼 각 트리 노드의 개수를 담는 배열 size[] 를 추가한 뒤 두 집합이 합쳐질 때마다 이 값을 갱신해 주면 된다.
• 이것을 이용하면 집합들이 합쳐지는 과정에서 가장 큰 집합의 크기가 어떻게 변하는지 구현할 수 있다.

 

Reference

• 도서 : 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략