Union-Find (Disjoint Set)

1. Union-Find

Union-Find란 서로소 집합(Disjoint Set)을 관리하는 자료구조다. 여러 개의 원소, 여러 개의 집합이 있다고 가정했을 때 특정 원소가 어떤 집합에 속해있는지 확인하거나 특정 집합을 합쳐야 할 일이 있다면 Union-Find 자료구조를 사용한다.

💡 서로소란?
겹치는 원소가 없는 그룹들

Union-Find의 원리는 다음의 영상에서 잘 나타나있다. https://www.youtube.com/watch?v=ayW5B2W9hfo

 

예를 들면, 다음과 같은 경우에 사용한다.

1. 사이클 판별: 빠르게 연결 여부를 확인할 수 있다.
2. MST(크루스칼 알고리즘): 안전한 간선만 선택할 수 있다.
3. 집합의 수 세기: 루트만 추적하면 바로 카운트할 수 있다.

즉, 연결되어 있는지, 같은 그룹인지를 빠르게 확인해 주는 알고리즘이다.

이렇게 기본적인 Union-Find를 구현하면 시간 복잡도가 트리의 높이 H에 따라 O(H)가 된다.

class Solution {
    private int[] parent; // 각 노드의 부모를 저장하는 배열
    
    public int solution(int size) {
        parent = new int[size];
        for (int i=0; i<size; i++)
            uf[i] = i; // 처음엔 자기 자신이 부모
    }
    
    // find 함수: x가 속한 집합의 루트를 찾는 함수
    // x가 루트 노드라면 x 값을 반환한다. x가 루트 노드가 아니라면, x의 부모인 uf[x]에서 더 탐색을 진행한다.
    public int find(int x) {
        if (parent[x] == x) return x;
        return find(parent[x]);
    }
    
    // union 함수: 두 집합을 하나로 합치는 합수
    // x의 루트를 y의 루트에 붙인다.
    public void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a < b) parent[b] = a;
        else parent[a] = b;
    }
}

 

2. 경로 압축

위의 Union-Find 구현의 경우, 모든 집합들이 합쳐져 있는 경우에는 조상을 찾을 때까지 계속 앞으로 나아가야 하고 최악의 경우(한쪽으로 쏠린 경우) O(N)의 시간이 소요된다.

find를 호출할 때 조상을 찾아낸 경우 현재 값의 부모 값을 조상으로 바꿔버리는 방법을 통해 이 문제를 해결할 수 있다.

이렇게 되면 find 함수가 호출될 때마다 탐색했던 모든 노드가 전부 root로 붙어 깊이가 1로 바뀌므로, 이후 동일한 노드를 탐색할 때 시간이 거의 소요되지 않게 된다. 즉, 중복 탐색하는 경우가 많이 사라지게 된다.

이렇게 구현하면 union, find 함수의 시간복잡도가 모두 O(logN)이 된다.

class Solution {
    private int[] parent;
    
    public int solution(int size) {
        parent = new int[size];
        for (int i=0; i<size; i++)
            uf[i] = i;
    }
    
    public void find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(x);
    }
    
    public void union(int a, int b) {
        a = find[a];
        b = find[b];
        if (a < b) parent[b] = a;
        else parent[a] = b;
    }
}