유니온파인드(Union-Find) 알고리즘: 기본 개념과 최적화 기법

서로소 집합

 

공통원소가 없는 두 집합

 

서로소 집합은 대표적으로 두 가지 연산을 수행합니다

 

1. Find(X): X가 속한 집합의 대표 찾기

2. Union(X, Y) : X가 속한 집합과 Y가 속한 집합을 합침

 

따라서 서로소 집합을 이용하는 알고리즘을 유니온파인드라고 말합니다

 

유니온파인드 연산

 

일반적인 배열을 사용해서도 유니온파인드 연산을 수행할 수 있습니다

이 경우 Union연산 수행을 위해 배열의 모든 값을 돌면서 대표를 변경해야하므로 시간복잡도는 O(N)입니다

유니온파인드 알고리즘을 사용하는 이유는 이 시간복잡도를 O(a(N)), 약 O(1)의 시간복잡도로 줄이기 위해서입니다

 

최초에는 각 원소는 각자 자신이 대표가 됩니다

 

원소	0	1	2	3	4
대표	0	1	2	3	4

 

- Find

 

임의로 1번 원소를 0번 집합에 포함시키고 2번 원소를 1번 집합에 포함시키겠습니다

 

원소	0	1	2	3	4
대표	0	0	1	3	4

 

2번 원소의 대표는 어떻게 찾을까요? 원소 == 대표가 될때까지 대표를 따라 이동하면 됩니다

 

    private int[] parent;

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

 

그러나 이 코드는 최악의 경우, 모든 원소가 일렬로 연결된 경우(예: 0 - 1 - 2 - 3 - 4)에는 O(N)의 시간 복잡도를 가집니다.

 

시간복잡도를 줄이기 위해서 find로 대표 원소를 찾으면 대표값을 바로 위 집합의 원소가 아니라 대표 원소로 변경해줍시다

 

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

 

이제 find 함수를 실행하면 배열은 다음과 같이 변경되고 find의 시간복잡도는 거의 O(1)이 됐습니다

 

원소	0	1	2	3	4
대표	0	0	0	3	4

 

- Union

 

이번에는 임의로 합치지 않고 실제로 합치는 Union 함수를 구현해보겠습니다

Union 함수는 각 대표값을 찾고 한쪽의 대표를 반대쪽 대표로 변경해주면 됩니다

 

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

 

union(3, 4)로 합치면 배열은 다음과 같이 변경됩니다

 

원소	0	1	2	3	4
대표	0	0	0	4	4

 

이 메서드에도 한 가지 추가적으로 고려할 점이 있습니다

배열이 다음과 같다고 가정합시다

 

원소	0	1	2	3	4
대표	0	0	1	4	4

 

Union을 아무렇게나 합쳐도 괜찮을까요?

현재 0 집합의 최대 깊이는 2, 4집합의 최대 깊이는 1입니다

2의 깊이는 2이고 4의 깊이는 0입니다

 

union(4 , 2)를 수행할 경우

원소	0	1	2	3	4
대표	0	0	1	4	0

 

최대 깊이는 여전히 0 - 1 - 2로 변하지 않습니다

 

union(2, 4)를 수행할 경우

원소	0	1	2	3	4
대표	4	0	1	4	4

 

최대 깊이는 4 - 0 - 1 - 2로 깊이가 1증가했습니다

 

즉, 트리의 깊이가 큰 쪽을 작은쪽으로 합치는 경우 트리의 깊이가 계속 증가하여 시간복잡도는 O(N)이 되고

깊이가 작은 쪽을 큰 쪽으로 합치는 경우 시간복잡도는 거의 O(1)로 줄일 수 있으므로 항상 깊이가 작은 쪽을 큰 쪽으로 합치도록 코드를 수정하겠습니다

 

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

        if (rootX == rootY) return;

        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }

 

이 코드는 깊이가 작은 쪽을 큰 쪽으로 합칩니다. 이 경우, 트리의 깊이는 변하지 않습니다.

 

만일 두 깊이가 동일한 경우 깊이는 1 증가합니다

 

최종적인 유니온 파인드 코드는 다음과 같습니다

 

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) return;

        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

 

유니온파인드 대표 연산

 

- 원소가 속한 집합의 대표 찾기 : find(x)

- 두 원소가 같은 집합에 속하는지 확인 : find(x) == find(y)

- 두 집합을 합치기(커뮤니티에 포함, 합병) : union(x)

- 집합 갯수 세기 : 대표값을 모은 Set의 크기 계산

- 그래프에 사이클을 포함하는지 확인 : find(node1) == find(node2)이면 두 노드 간 사이클 존재

- 최소 스패닝 트리 : 간선의 가중치가 작은 순서로 처리하면서 find(node1) != find(node2) 이면 union(node1, node2)