[Algorithm] 유니온 파인드(Union-Find) 알고리즘

유니온 파인드(Union-Find) 알고리즘이란

유니온 파인드 알고리즘은 대표적인 그래프 알고리즘 중 하나로, 주어진 그래프의 노드들을 서로 다른 집합으로 분리하거나, 두 개의 노드가 같은 집합에 속하는지 여부를 판단하는 데 사용됩니다.

 

이 알고리즘은 일반적으로 노드들이 상호 연결된 그래프에서 사용됩니다. 초기에는 모든 노드들이 각각 서로 다른 집합에 속해 있습니다. 유니온 파인드 알고리즘은 두 개의 노드가 같은 집합에 속하도록 하거나, 두개의 집합을 하나로 합치는 연산을 수행합니다.

 

이 알고리즘의 핵심은 각각의 집합을 하나의 트리로 나타내는 것 입니다. 각 노드는 해당 집합의 루트 노드를 가리키는 포인터를 가지고 있습니다. 노드들이 합쳐지면, 두 트리의 루트 노드를 연결하고, 이전에 각 트리의 루트 노드를 가리키던 노드들은 새로운 루트 노드를 가리키도록 업데이트가 됩니다.

 

유니온 파인드 알고리즘은 트리의 높이에 따라서 성능이 크게 달라질 수 있습니다. 따라서 경로 압축(path compression)이나 (rank)기반의 최적화를 적용하여 성능을 개선할 수 있습니다.

 

코드

public 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;
        }
    }

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

    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[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
}

UnionFind 클래스는 parent 배열과 rank 배열을 사용하여 유니온 파인드 알고리즘을 구현합니다. parent 배열은 각 노드의 부모 노드를 저장하고, rank 배열은 각 노드의 깊이를 저장합니다.

find 메서드는 재귀적으로 각 노드의 루트 노드를 찾아 반환합니다. 이때, 경로 압축 최적화를 적용하여 재귀호출을 할 때마다 노드의 부모 노드를 루트 노드로 업데이트합니다.

union 메서드는 두 개의 노드가 속한 집합을 합치는 메서드입니다. find 메서드는 두 개의 노드가 속한 집합을 하나로 합치는 메서드입니다. find 메서드를 사용하여 두 노드의 루트 노드를 찾은 다음 rank 배열을 기반으로 더 깊은 루트로 삼도록 연결합니다. 두 트리의 깊이가 같은 경우에는 한쪽의 루트를 다른 쪽의 자식으로 만들어주고, 해당 트리의 깊이를 1 증가시킵니다. 이렇게 함으로써 트리의 높이를 최소화할 수 있습니다. 

 

시간복잡도와 공간복잡도

• 시간복잡도 : O(m * α(n)), 여기서 m은 union 또는 find 연산의 총 수이고, α(n)은 애커만 함수(Ackermann function)의 역함수로, n이 어떤 값이든 상수 시간 안에 수렴하는 값입니다. 일반적으로 α(n)은 매우 작은 값으로, 상수 시간 안에 수렴합니다.
• 공간복잡도 : O(n), 여기서 n은 노드의 개수입니다. 유니온 파인드 알고리즘에서는 각 노드마다 하나의 원소를 저장하기 때문에, 전체 노드의 개수만큼의 공간이 필요합니다.

유니온 파인드 알고리즘의 시간복잡도는 상당히 빠른 편에 속합니다. 최악의 경우에도 O(m * α(n))의 시간복잡도를 가지므로, 대부분의 상황에서 충분히 효율적으로 동작할 수 있습니다. 공간복잡도도 노드의 개수에 비례하는 정도로 매우 작습니다. 따라서 유니온 파인드 알고리즘은 대부분의 그래프 알고리즘에서 유용하게 사용됩니다.