유니온-파인드 알고리즘

유니온-파인드(Union-Find) 알고리즘은 여러 집합을 효율적으로 관리하는 데 사용되는 알고리즘이다. 주로 서로소 집합(disjoint-set)을 다루는 데에 활용된다. 유니온-파인드 알고리즘은 각 집합을 대표하는 원소를 찾거나, 두 집합을 합치는 등의 연산을 수행할 수 있다. 대표적으로 "합집합 찾기(Union)"와 "찾기(Find)" 연산이 있다.

간단한 버전

class UnionFind {
    private final int[] parent;

    public UnionFind(int size) {
        this.parent = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
   
    // 집합의 개수
    public int countSets() {
            int count = 0;
            for (int i = 0; i < parent.length; i++) {
                if (parent[i] == i) {
                    count++;
                }
            }
            return count;
    }
}

 

Rank사용 버전

rank 배열을 사용하여 각 집합의 랭크를 유지하고, 랭크를 비교하여 합치는 과정을 수행한다.
랭크가 낮은 트리를 높은 트리에 합치면서 트리의 높이를 최소화한다.
 

class UnionFind {
    private int[] parent;
    private int[] rank;

    // 생성자: 초기화
    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];

        for (int i = 0; i < size; i++) {
            parent[i] = i;  // 초기에는 각 원소가 자기 자신을 가리키도록 초기화
            rank[i] = 0;    // 초기에는 각 원소의 랭크가 0
        }
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        // 두 집합의 루트가 같으면 이미 같은 집합에 속해 있는 것이므로 더 이상의 작업 필요 없음
        if (rootX != rootY) {
            // 랭크를 기준으로 더 낮은 랭크를 가진 집합을 높은 랭크를 가진 집합에 합침
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootX] = rootY;
                rank[rootY]++;
            }
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
}

 

집합의 사이즈를 관리하는 버전

class UnionFind {
    private final int[] parent;
    private final int[] size;

    public UnionFind(int n) {
        this.parent = new int[n];
        this.size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            // y가 속한 집합 밑으로 새롭게 편입한다.
            // y가 속한 집합에 부모를 x가 속합 집합에 부모로 한다.
            parent[rootX] = rootY;
            // y가 속합 집합의 크기를 x가 속한 집합의 크기와 더한다.
            size[rootY] += size[rootX];
        }
    }

    public int find(int x) {
        // 혼자 속한 집합이 아니라면
        if (parent[x] != x) {
            // x가 속한 집합의 부모를 찾아서
            // x의 부모로 한다. (경로 축소)
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public int getSize(int x) {
        int rootX = find(x);
        return size[rootX];
    }
}