동적 연결성

동적 연결성(Dynamic Connectivity) 문제는 객체들 사이의 연결 관계가 순차적으로 입력으로 주어질 때, 임의의 두 객체가 서로 같은 집합에 속하는지를 빠르게 판단하는 문제다. 이 때 "연결됨"은 다음 세 가지 조건을 만족하는 동치 관계(Equivalence Relation)로 볼 수 있다.

• 반사성: 모든 객체는 자기 자신과 연결된다.
• 대칭성: p가 q와 연결되면 q도 p와 연결된다.
• 이성: p가 q와 연결되고 q가 r과 연결되면 p와 r도 연결된다.

이 동치 관계는 전체 객체를 여러 개의 연결 요소(Connected Component)로 나눈다. Union-Find 알고리즘의 목표는 입력된 (p, q) 쌍에 대해, 두 객체가 이미 같은 연결 요소에 속하면 무시하고, 그렇지 않으면 두 집합을 합치는 것이다.

추상화된 API

문제를 해결하기 위해 다음과 같은 인터페이스를 정의한다. 각 메서드는 0 이상 n 미만의 정수로 표현된 노드를 대상으로 동작한다.

public interface IDisjointSet
{
    int Find(int x);
    void Union(int a, int b);
    bool Same(int a, int b);
    int Count { get; }
}

• Find: 주어진 노드가 속한 집합의 대표 노드를 반환한다.
• Union: 두 노드가 속한 집합을 합다.
• Same: 두 노드가 같은 집합에 속하는지 확인한다.
• Count: 현재 연결 요소의 개수를 반환한다.

Quick-Find

Quick-Find는 같은 집합에 속한 모든 노드가 같은 식별자를 도록 label 배열을 관리한다. 합을 합칠 때는 한 집합에 속한 모든 노드의 식별자를 다른 집합의 식별자로 바꿔야 한다.

public class QuickFindSet : IDisjointSet
{
    private int[] label;
    private int components;

    public QuickFindSet(int n)
    {
        label = new int[n];
        for (int i = 0; i < n; i++)
            label[i] = i;
        components = n;
    }

    public int Find(int x) => label[x];

    public bool Same(int a, int b) => Find(a) == Find(b);

    public void Union(int a, int b)
    {
        int idA = Find(a);
        int idB = Find(b);

        if (idA == idB)
            return;

        for (int i = 0; i < label.Length; i++)
        {
            if (label[i] == idB)
                label[i] = idA;
        }
        components--;
    }

    public int Count => components;
}

Quick-Find에서 Find는 O(1)이지만 Union은 전체 배열을 스해야 하므로 O(N)이다. N개의 노드가 하나의 집합으로 합쳐지는 최악의 경우 총 배열 접근 횟수는 O(N²) 수준이다.

Quick-Union

Quick-Union은 각 노드가 같은 집합 내 다른 노드를 가리키도록 parent 배열을 사용한다. 집합의 대표는 자기 자신을 가리키는 루트 노드다.

public class QuickUnionSet : IDisjointSet
{
    private int[] parent;
    private int components;

    public QuickUnionSet(int n)
    {
        parent = new int[n];
        for (int i = 0; i < n; i++)
            parent[i] = i;
        components = n;
    }

    public int Find(int x)
    {
        while (parent[x] != x)
            x = parent[x];
        return x;
    }

    public bool Same(int a, int b) => Find(a) == Find(b);

    public void Union(int a, int b)
    {
        int rootA = Find(a);
        int rootB = Find(b);

        if (rootA == rootB)
            return;

        parent[rootA] = rootB;
        components--;
    }

    public int Count => components;
}

이 구현은 Union 연산을 빠르게 만들지만, 루트를 찾기 위한 경로가 길어질 수 있다. 예를 들어 0-1, 0-2, 0-3 순으로 연결되면 한쪽으로 편향된 긴 트리가 만들어진다. 이 경우 Find의 비용은 트리 높이에 비례하며, 최악에는 O(N)이 되어 전체 복잡도가 O(N²)로 다시 증가할 수 있다.

Weighted Quick-Union

Quick-Union의 단점은 합칠 때 어떤 트리를 루트로 붙일지 임의로 정한다는 점이다. 이를 개선하여 항상 작은 트리를 큰 트리 밑에 붙이는 방식을 Weighted Quick-Union이라 한다. 각 트리의 노드 개수를 groupSize 배열로 관리한다.

public class WeightedUnionSet : IDisjointSet
{
    private int[] parent;
    private int[] groupSize;
    private int components;

    public WeightedUnionSet(int n)
    {
        parent = new int[n];
        groupSize = new int[n];
        for (int i = 0; i < n; i++)
        {
            parent[i] = i;
            groupSize[i] = 1;
        }
        components = n;
    }

    public int Find(int x)
    {
        while (parent[x] != x)
            x = parent[x];
        return x;
    }

    public bool Same(int a, int b) => Find(a) == Find(b);

    public void Union(int a, int b)
    {
        int rootA = Find(a);
        int rootB = Find(b);

        if (rootA == rootB)
            return;

        if (groupSize[rootA] < groupSize[rootB])
        {
            parent[rootA] = rootB;
            groupSize[rootB] += groupSize[rootA];
        }
        else
        {
            parent[rootB] = rootA;
            groupSize[rootA] += groupSize[rootB];
        }
        components--;
    }

    public int Count => components;
}

큰 리를 루트로 삼으면 모든 노드의 이가 로그로 제한된다. 따라서 트리의 이는 O(log N)을 넘지 않으며, Find와 Union 연산 모두 O(log N) 시간에 수행된다.

경로 압축(Path Compression)

Weighted Quick-Union에 경로 압을 결합하면 거의 상수 시간에 수행된다. Find를 수행하면서 경로 상의 모든 노드를 루트에 직접 연결하면 후속 검색에서 깊이를 1로 만들 수 있다.

public class CompressedUnionSet : IDisjointSet
{
    private int[] parent;
    private int[] groupSize;
    private int components;

    public CompressedUnionSet(int n)
    {
        parent = new int[n];
        groupSize = new int[n];
        for (int i = 0; i < n; i++)
        {
            parent[i] = i;
            groupSize[i] = 1;
        }
        components = n;
    }

    public int Find(int x)
    {
        int root = x;
        while (parent[root] != root)
            root = parent[root];

        while (parent[x] != root)
        {
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }

    public bool Same(int a, int b) => Find(a) == Find(b);

    public void Union(int a, int b)
    {
        int rootA = Find(a);
        int rootB = Find(b);

        if (rootA == rootB)
            return;

        if (groupSize[rootA] < groupSize[rootB])
        {
            parent[rootA] = rootB;
            groupSize[rootB] += groupSize[rootA];
        }
        else
        {
            parent[rootB] = rootA;
            groupSize[rootA] += groupSize[rootB];
        }
        components--;
    }

    public int Count => components;
}

경로 압축을 적용하면 평균적으로 거의 O(1)에 가까운 성능을 얻는다. 이론적으로는 Inverse Ackermann 함수 α(N)에 비례하는 시간이 소요되며, 이는 실용적으로 5 이하의 작은 상수로 볼 수 있다.

복잡도 비교