2-9. 자료구조: Disjoint Set (Union-Find)

1. Disjoint Set (Union-Find) 소개

Disjoint Set 자료구조는 서로소 집합(Disjoint Sets), 즉 공통 원소가 없는 부분 집합들로 이루어진 집합들을 관리하는 데 특화된 자료구조입니다. 이 자료구조는 Union-Find 알고리즘을 사용하여 집합 간의 합치기(Union) 연산과 특정 원소가 속한 집합을 찾는(Find) 연산을 효율적으로 수행합니다. 이러한 특징 때문에, 그래프 이론, 네트워크 연결, 클러스터링 등 다양한 분야에서 활용됩니다.

1) 배경

Disjoint Set 자료구조는 특히 동적 연결성 문제(Dynamic Connectivity Problem)를 해결하는 데 효과적입니다. 동적 연결성 문제는 그래프에서 노드 간의 연결 관계가 시간에 따라 변동할 때, 두 노드가 같은 연결 요소(Connected Component)에 속하는지 효율적으로 판단해야 하는 문제입니다. 예를 들어, 소셜 네트워크에서 친구 관계가 추가되거나 삭제될 때, 두 사람이 간접적으로 친구 관계인지 판단하는 경우에 활용될 수 있습니다.

2) 비유

Disjoint Set을 이해하기 위한 비유로, 여러 개의 섬과 다리를 생각해 볼 수 있습니다. 각 섬은 서로소 집합을 나타내고, 다리는 두 섬을 연결하는 Union 연산을 의미합니다. Find 연산은 특정 섬에서 시작하여 다른 섬으로 이동할 수 있는지 확인하는 것입니다. 처음에는 각 섬이 독립적으로 존재하지만, 다리가 놓이면서 섬들은 점차적으로 연결되고, 결국에는 하나의 큰 섬으로 합쳐질 수 있습니다.

2. 핵심 원리: Union-Find 알고리즘

Union-Find 알고리즘은 두 가지 핵심 연산으로 구성됩니다.

1) Find 연산

Find 연산은 특정 원소가 속한 집합의 대표 원소(Representative Element)를 찾는 연산입니다. 대표 원소는 해당 집합을 대표하는 일종의 "우두머리"와 같습니다. Find 연산의 목표는 주어진 원소가 어떤 우두머리(대표 원소)를 따르는지, 즉 어떤 집합에 속하는지를 파악하는 것입니다.

알고리즘은 다음과 같습니다.

1. 초기 상태: 각 원소는 자신을 대표 원소로 하는, 즉 자신만을 포함하는 집합에 속합니다.
2. 재귀적 탐색: 주어진 원소의 부모 노드를 따라 올라가면서, 최종적으로 대표 원소를 찾습니다.
3. 경로 압축 (Path Compression): Find 연산의 효율성을 높이기 위해 경로 압축 기법을 사용합니다. 경로 압축은 Find 연산을 수행하는 과정에서, 탐색 경로 상의 모든 노드의 부모를 대표 원소로 직접 연결하는 최적화 기법입니다. 이를 통해 Find 연산의 시간 복잡도를 평균적으로 $O(\alpha(n))$으로 줄일 수 있습니다. 여기서 $\alpha(n)$은 아커만 함수의 역함수로, 실제로 매우 작은 값(거의 상수)을 가집니다.

2) Union 연산

Union 연산은 두 개의 집합을 하나로 합치는 연산입니다. 이 연산은 두 집합의 대표 원소를 찾고, 한쪽의 대표 원소를 다른 쪽의 대표 원소의 부모로 설정함으로써 두 집합을 병합합니다.

알고리즘은 다음과 같습니다.

1. Find 수행: 합치려는 두 원소 각각에 대해 Find 연산을 수행하여 각자의 대표 원소를 찾습니다.
2. 병합: 두 대표 원소가 다르다면, 한쪽의 대표 원소를 다른 쪽의 대표 원소의 부모로 설정하여 두 집합을 합칩니다. 이때, 일반적으로 더 작은 집합을 더 큰 집합에 병합하는 "랭크에 의한 Union" 기법을 사용하여 트리의 높이를 균형 있게 유지하고, Find 연산의 성능을 향상시킵니다.

3) 랭크에 의한 Union (Union by Rank)

랭크에 의한 Union은 Union 연산의 효율성을 높이기 위한 기법입니다. 각 노드는 랭크(rank)라고 하는 값을 가지며, 이는 해당 노드를 루트로 하는 서브트리의 높이에 대한 근사치입니다.

• Union 연산 시, 랭크가 낮은 트리를 랭크가 높은 트리에 병합합니다.
• 만약 랭크가 같다면, 한쪽 트리를 다른 쪽에 병합하고, 병합된 트리의 랭크를 1 증가시킵니다.

이 기법은 트리의 높이를 균형 있게 유지하여 Find 연산의 시간 복잡도를 개선하는 데 기여합니다.

4) 시간 복잡도

• Find 연산: $O(\alpha(n))$, 여기서 $\alpha(n)$은 아커만 함수의 역함수
• Union 연산: $O(\alpha(n))$
• m개의 Union-Find 연산: $O(m \alpha(n))$

3. 구현 (C++)

Disjoint Set 자료구조는 일반적으로 배열 또는 연결 리스트를 사용하여 구현할 수 있습니다. 각 원소는 자신의 부모 노드를 가리키는 포인터(또는 인덱스)를 가지며, 루트 노드는 자기 자신을 부모로 가리킵니다.

#include <vector>

class DisjointSet {
public:
    DisjointSet(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i; // 초기화: 각 노드는 자기 자신을 부모로
        }
    }

    // Find 연산 (경로 압축)
    int find(int u) {
        if (parent[u] == u) {
            return u;
        }
        return parent[u] = find(parent[u]); // 경로 압축
    }

    // Union 연산 (랭크에 의한 Union)
    void unite(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);

        if (rootU != rootV) {
            if (rank[rootU] < rank[rootV]) {
                parent[rootU] = rootV;
            } else if (rank[rootU] > rank[rootV]) {
                parent[rootV] = rootU;
            } else {
                parent[rootV] = rootU;
                rank[rootU]++;
            }
        }
    }

private:
    std::vector<int> parent; // 각 노드의 부모 노드를 저장
    std::vector<int> rank;   // 각 노드의 랭크 (트리 높이의 근사치)
};

4. 응용 및 활용 사례

1) 그래프의 사이클 감지

Disjoint Set은 그래프 내의 사이클을 감지하는 데 유용하게 사용됩니다. 간선을 하나씩 추가하면서, 해당 간선의 두 노드가 같은 집합에 속해 있는지 확인합니다. 만약 두 노드가 같은 집합에 속해 있다면, 사이클이 발생했음을 의미합니다.

2) 최소 신장 트리 (Minimum Spanning Tree, MST)

크루스칼 알고리즘(Kruskal's algorithm)은 Disjoint Set을 사용하여 최소 신장 트리를 찾습니다. 간선을 가중치 순으로 정렬한 후, 각 간선을 하나씩 추가하면서 두 노드가 다른 집합에 속해 있다면, Union 연산을 수행하여 두 집합을 합칩니다.

3) 네트워크 연결 문제

Disjoint Set은 네트워크에서 노드 간의 연결 상태를 관리하는 데 사용됩니다. 노드 간의 연결이 추가되거나 삭제될 때, Union 및 Find 연산을 사용하여 연결성을 효율적으로 파악할 수 있습니다.

4) 클러스터링

데이터 클러스터링 문제에서, Disjoint Set은 데이터를 그룹으로 묶는 데 사용될 수 있습니다. 유사한 데이터 포인트를 연결하고, 연결된 포인트들을 같은 집합으로 묶습니다.

5) 게임 맵 생성

게임 맵을 생성할 때, 맵의 타일들이 연결되어 있는지 확인하고, 연결된 타일들을 하나의 지역으로 묶는 데 사용할 수 있습니다.

5. 주의사항과 트러블슈팅

1) 초기화

Disjoint Set을 사용할 때, 각 원소를 자신만의 집합으로 초기화하는 것이 중요합니다. 이는 Find 연산이 올바르게 동작하기 위한 기본 전제 조건입니다.

2) 랭크에 의한 Union

랭크에 의한 Union은 Union 연산의 성능을 향상시키기 위해 중요한 기법입니다. 랭크를 올바르게 관리하지 않으면, 트리의 불균형이 발생하여 Find 연산의 성능이 저하될 수 있습니다.

3) 경로 압축

경로 압축은 Find 연산의 성능을 최적화하는 핵심 기법입니다. Find 연산을 수행할 때마다 경로 압축을 적용해야 합니다.

4) 자료형 선택

Disjoint Set을 구현할 때, 사용되는 데이터의 자료형에 유의해야 합니다. 예를 들어, 그래프의 노드 수가 매우 큰 경우, int 대신 long long과 같은 더 큰 자료형을 사용해야 할 수 있습니다.

5) 디버깅

Disjoint Set의 구현 및 활용 과정에서 오류가 발생할 경우, 각 연산의 결과를 추적하고, 그래프 구조를 시각화하여 디버깅하는 것이 도움이 될 수 있습니다.

6. 결론

Disjoint Set 자료구조는 Union-Find 알고리즘을 통해 집합 간의 합치기 및 찾기 연산을 효율적으로 수행하는 강력한 도구입니다. 동적 연결성 문제, 그래프 알고리즘, 클러스터링 등 다양한 분야에서 활용되며, 문제 해결 능력을 향상시키는 데 기여합니다. 랭크에 의한 Union 및 경로 압축과 같은 최적화 기법을 적절히 활용하여 성능을 극대화할 수 있습니다.