유니온 파인드(Union-Find)

서로소 집합(Disjoint Set)이란?

공통 원소가 없는 두 집합, 즉 A∩B=∅을 만족시키는 두 집합 A, B를 서로소 집합이라고 한다.

유니온 파인드(Union-Find)란?

서로소 집합에 대한 연산을 할 때 사용하는 알고리즘이다. 쉬운 이해를 위해 다음의 예시를 보자.

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

위의 문제처럼 초기에 n+1개의 집합  {0}, {1}, {2}, ... , {n}이 있고 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 할 때 사용하면 좋은 알고리즘이 유니온 파인드이다.

즉, 유니온 파인드는 각 서로소 집합에 대한 합집합 연산과 두 원소가 같은 집합에 포함되어 있는지를 쉽고 빠르게 확인할 수 있게 하는 알고리즘인 것이다. 이 문제에 대한 Java 풀이는 다음 접은글과 같다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void make_set(int[] parent, int x) {
        parent[x] = x;
    }
    
    public static int find_set(int[] parent, int x) {
        if (parent[x] == x) return x;
        else return parent[x] = find_set(parent, parent[x]);
    }

    public static void union_set(int[] parent, int a, int b) {
        a = find_set(parent, a);
        b = find_set(parent, b);
        parent[b] = a;
    }

    public static boolean is_union(int[] parent, int a, int b) {
        a = find_set(parent, a);
        b = find_set(parent, b);
        return a == b;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] parent = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            make_set(parent, i);
        }
        StringBuilder sb = new StringBuilder();
        while (m-- > 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int op = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            if (op == 0) {
                union_set(parent, a, b);
            } else if (is_union(parent, a, b)) {
                sb.append("YES\n");
            } else {
                sb.append("NO\n");
            }
        }
        System.out.print(sb);
    }
}

유니온 파인드의 주요 연산

• make_set(p, x) : 노드 x를 유일한 원소로 하는 집합 생성
• union_set(p, a, b) : 노드 a가 속한 집합과 노드 b가 속한 집합에 대한 합집합 연산
• find_set(p, x) : 노드 x가 속한 트리의 루트 노드를 반환
• is_union(p, a, b) : 노드 a가 속한 집합과 노드 b가 속한 집합이 같은 집합인지 여부 반환

find_set 연산을 보면 어떤 노드가 속한 트리라고 했다. 분명 위에서 집합과 관련된 연산이라고 했는데 왜 트리가 나올까?

그 이유는 유니온 파인드 알고리즘을 사용할 때 집합을 다음과 같 트리 구조로 표현하기 때문이다.

---

유니온 파인드 구현

void make_set(int parent[], int x) {
	parent[x] = x;
}
int find_set(int parent[], int x) {
	if (parent[x] == x) return x;
	else return find_set(parent, parent[x]);
}
void union_set(int parent[], int a, int b) {
	a = find_set(parent, a);
	b = find_set(parent, b);
	parent[b] = a;
}
int is_union(int parent[], int a, int b) {
	a = find_set(parent, a);
	b = find_set(parent, b);
	return a == b ? 1 : 0;
}

위와 같이 유니온 파인드를 구현하면 find_set 연산을 실행할 때마다 x의 루트 노드를 찾을 때까지 find_set 함수를 재귀적으로 실행할 것이다. 그래서 다음과 같이 경로 압축을 사용하여 find_set 함수를 실행하는 과정에서 만나는 모든 노드들이 직접 루트 노드를 가리키도록 수정해보자.

int find_set(int parent[], int x) {
	if (parent[x] == x) return x;
	else return parent[x] = find_set(parent, parent[x]);
}

위의 코드 또한 문제가 있다. 이러한 유니온 파인드 연산의 실행 시간은 트리의 높이에 영향을 받는데 위의 코드대로 실행한다면 최악의 경우에 높이가 높은 트리가 그렇지 않은 트리에 연결되는 것이 반복된다면 전체적으로 트리의 높이는 반대로 반복된 경우보다 훨씬 높아지게 될 것이다. 그렇기 때문에 다음과 같이 make_set 연산과 union_set 연산을 유니온 바이 랭크(Union by Rank)를 사용하여 성능을 향상시킬 수 있다.

void make_set(int parent[], int rank[], int x) {
	parent[x] = x;
	rank[x] = 0;
}
void union_set(int parent[], int rank[], int a, int b) {
	a = find_set(parent, a);
	b = find_set(parent, b);
	if (rank[a] > rank[b]) {
        parent[b] = a;
    }
    else {
        parent[a] = b;
        if (rank[a] == rank[b]) {
            rank[b]++;
        }
    }
}

전체 코드는 다음과 같다.

void make_set(int parent[], int rank[], int x) {
	parent[x] = x;
	rank[x] = 0;
}
int find_set(int parent[], int x) {
	if (parent[x] == x) return x;
	else return parent[x] = find_set(parent, parent[x]);
}
void union_set(int parent[], int rank[], int a, int b) {
	a = find_set(parent, a);
	b = find_set(parent, b);
	if (rank[a] > rank[b]) {
        parent[b] = a;
    }
    else {
        parent[a] = b;
        if (rank[a] == rank[b]) {
            rank[b]++;
        }
    }
}
int is_union(int parent[], int a, int b) {
	a = find_set(parent, a);
	b = find_set(parent, b);
	return a == b ? 1 : 0;
}