[JAVA] Union-Find 알고리즘

Union-Find 알고리즘

공통 원소가 없는 두 집합을 서로소 집합이라고 한다. Union-Find 알고리즘은 많은 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하는 자료구조를 나타낸다. 그래프 혹은 트리 자료구조에서 두 노드가 같은 그래프에 속해 있는지 알 수 있다.

 

서로소 집합은 기본적으로 세 가지 연산으로 구성되어 있다.

 

1. Make Set 연산

각 원소에 대해 집합을 만드는 연산으로, 자기 자신을 하나의 집합으로 만든다. 따라서 각 집합의 대표자는 원소 자신이 된다.

int[] parents = new int[N];

private static int makeSet() {
    for(int idx = 0; idx < parents.length; idx++) {
        parents[idx] = idx;
    }
}

 

2. find 연산

해당 원소의 대표자를 찾는 연산이다. 대표자를 찾을 때까지 재귀적으로 부모를 타고 올라간다.

private static int find(int x) {
    if(parent[x] == x) return x;
    else return find(parent[x]);
}

 

3. Union 연산

1번에서 만든 집합들을 알맞게 합쳐주는(union) 연산이다. 자신의 대표자를 상대 집합의 대표자로 변경해서 합쳐준다. 이 때 두 집합의 대표자가 다른 대표자를 부모로 삼도록 해야 한다. 자신 뿐만 아니라 자신이 속한 집합이 다른 집합에 합쳐져야 하기 때문이다.

private static void union(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    
    if(pa > pb) {
    	parent[pa] = pb;
    } else {
    	parent[pb] = pa;
    }
}

 

최적화: 경로 압축 (Path Compression)

위 코드대로 Union-Find 알고리즘을 구현하면, parent 배열은 각 원소의 부모를 나타내지만 대표자를 나타내지는 않는다. 만약 대표자를 찾고 싶다면 다시 find 연산을 수행해야 한다. 또한 find 연산은 호출 때마다 트리의 대표자(root)까지 재귀적으로 탐색하기 때문에 비효율적이다. 

경로 압축이란, 각 원소의 부모를 해당 원소의 대표자로 통일하는 방법이다. Union-Find 알고리즘은 두 원소가 같은 집합에 속해있는 지 아닌지만 판별하기 때문에 트리 구조를 유지할 필요는 없다.

이는 find 연산 내 재귀 연산을 수정해 반영할 수 있다.

private static int find(int x) {
    if(parent[x] == x) return x;
    else return parent[x] = find(parent[x]);
}