Union-Find 자료구조

본 블로그 작성 글들은, 강의를 목표로 하고 제작되었습니다. 또한 작성된 글의 정보도 틀렸을 수 있으니, 주의해주세요.

Union-Find는 여러 원소가 같은 집합에 속하는지 빠르게 확인하고 두 집합을 합치는 자료구조다. Disjoint Set Union, 줄여서 DSU라고도 부른다.

Parent로 대표를 찾는다

class DisjointSet
{
public:
    explicit DisjointSet(int Count)
        : Parent(Count), Rank(Count, 0)
    {
        std::iota(Parent.begin(), Parent.end(), 0);
    }

    int Find(int Value)
    {
        if (Parent[Value] != Value)
        {
            Parent[Value] = Find(Parent[Value]);
        }

        return Parent[Value];
    }

    bool Unite(int A, int B)
    {
        A = Find(A);
        B = Find(B);

        if (A == B)
        {
            return false;
        }

        if (Rank[A] < Rank[B])
        {
            std::swap(A, B);
        }

        Parent[B] = A;

        if (Rank[A] == Rank[B])
        {
            ++Rank[A];
        }

        return true;
    }

private:
    std::vector<int> Parent;
    std::vector<int> Rank;
};

Path Compression은 Find 과정에서 부모를 대표에 바로 연결한다. Union by Rank는 낮은 트리를 높은 트리 밑에 붙여 깊이가 커지는 것을 막는다.

두 최적화를 같이 사용하면 연산은 실제로 거의 상수 시간처럼 동작한다.

어디에 사용하는가?

• 두 지역이 연결되어 있는지 확인한다.
• 간선을 추가했을 때 Cycle이 생기는지 검사한다.
• Kruskal 알고리즘으로 최소 신장 트리를 만든다.
• 온라인으로 집합을 계속 합친다.

Union-Find는 경로 자체를 알려주지는 않는다. 연결 여부와 집합 병합이 목적일 때 강력한 자료구조다.