디스조인트 집합 (Disjoint Set)의 개념 및 구현

디스조인트 집합 (Disjoint Set)의 개념 및 구현

디스조인트 집합(Disjoint Set)은 겹치지 않는 여러 개의 집합을 효율적으로 관리하기 위한 자료구조입니다.
주로 집합 간의 결합(Union)과 원소의 대표 찾기(Find) 연산을 빠르게 수행하는 데 사용됩니다.
이 자료구조는 그래프의 연결성 확인과 최소 신장 트리 알고리즘(예: 크루스칼 알고리즘)에서 중요한 역할을 합니다.

---

1. 디스조인트 집합(Disjoint Set)이란?

디스조인트 집합은 다음과 같은 두 가지 기본 연산을 빠르게 수행하기 위한 자료구조입니다:

1. Find: 특정 원소가 속한 집합의 대표 원소를 찾습니다.
2. Union: 두 집합을 하나로 합칩니다.

이 자료구조는 특히 서로소 집합(겹치는 원소가 없는 집합)을 관리할 때 유용하며, 트리 기반 구조를 사용해 효율적인 구현이 가능합니다.

---

2. 디스조인트 집합의 주요 개념

2.1 대표 원소 (Representative Element)

각 집합에는 고유한 대표 원소가 있습니다. Find 연산을 통해 각 원소가 속한 집합의 대표 원소를 찾을 수 있습니다.

2.2 Union 연산

두 집합을 결합할 때 하나의 대표 원소를 다른 집합의 대표 원소에 연결합니다.

2.3 최적화 기법

디스조인트 집합은 다음 두 가지 기법을 활용해 성능을 극대화합니다:

• 경로 압축(Path Compression): Find 연산 중 방문한 모든 노드를 직접 대표 원소에 연결하여 트리의 높이를 줄입니다.
• 랭크 기반 합치기(Union by Rank): 두 집합을 결합할 때 트리의 높이가 낮은 집합을 높이가 높은 집합에 연결하여 트리의 균형을 유지합니다.

---

3. 디스조인트 집합의 시간 복잡도

위 두 가지 최적화 기법을 사용하면 각 연산의 시간 복잡도는 거의 상수 시간에 가깝습니다:

• Find: O(α(n)), 여기서 α(n)은 아커만 함수의 역함수로 매우 느리게 증가합니다.
• Union: O(α(n))

---

4. C#으로 디스조인트 집합 구현

다음은 C#을 사용하여 디스조인트 집합을 구현한 코드입니다:

using System;

public class DisjointSet
{
    private int[] parent; // 부모 노드 배열
    private int[] rank;   // 트리의 높이를 저장하는 배열

    // 생성자: 각 원소가 자기 자신을 부모로 가지는 초기 상태 설정
    public DisjointSet(int size)
    {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++)
        {
            parent[i] = i; // 자기 자신을 부모로 초기화
            rank[i] = 0;   // 초기 랭크는 0
        }
    }

    // Find: 원소 x가 속한 집합의 대표 원소를 찾음 (경로 압축 적용)
    public int Find(int x)
    {
        if (parent[x] != x)
        {
            parent[x] = Find(parent[x]); // 경로 압축
        }
        return parent[x];
    }

    // Union: 두 집합을 결합 (랭크 기반 합치기 적용)
    public void Union(int x, int y)
    {
        int rootX = Find(x);
        int rootY = Find(y);

        if (rootX != rootY)
        {
            // 랭크 비교 후 결합
            if (rank[rootX] > rank[rootY])
            {
                parent[rootY] = rootX;
            }
            else if (rank[rootX] < rank[rootY])
            {
                parent[rootX] = rootY;
            }
            else
            {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
}

// 사용 예제
public class Program
{
    public static void Main()
    {
        DisjointSet ds = new DisjointSet(5);

        ds.Union(0, 1);
        ds.Union(1, 2);

        Console.WriteLine(ds.Find(0)); // 출력: 0
        Console.WriteLine(ds.Find(1)); // 출력: 0
        Console.WriteLine(ds.Find(2)); // 출력: 0
        Console.WriteLine(ds.Find(3)); // 출력: 3

        ds.Union(3, 4);
        Console.WriteLine(ds.Find(4)); // 출력: 3
    }
}

 

---

5. 디스조인트 집합의 활용 사례

5.1 최소 신장 트리 (MST)

• 크루스칼 알고리즘에서 간선 연결 시 두 정점이 같은 집합에 속해 있는지 확인하는 데 사용됩니다.

5.2 연결된 컴포넌트

• 그래프에서 연결된 컴포넌트를 찾는 데 활용됩니다.

5.3 네트워크 연결 확인

• 컴퓨터 네트워크에서 두 장치가 연결되어 있는지 확인합니다.

5.4 친구 관계 문제

• 소셜 네트워크에서 친구 그룹을 관리하거나 연결성을 확인하는 데 유용합니다.

---

6. 디스조인트 집합의 장단점

장점

• 효율적인 연산: O(α(n))로 매우 빠른 속도 제공.
• 다양한 그래프 알고리즘에서 필수적.

단점

• 초기 구현이 복잡할 수 있음.
• 응용에 따라 최적화가 필요.

---

디스조인트 집합은 그래프 알고리즘과 집합 관리 문제에서 매우 중요한 자료구조입니다.
특히 최소 신장 트리, 네트워크 연결 확인, 친구 관계 관리 등 다양한 문제를 효율적으로 해결하는 데 사용됩니다.