서로소 집합(Disjoint Set)

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

서로 공통된 원소를 갖고 있지 않은 두 개 이상의 집합
즉, 교집합이 없는 집합들을 관리하는 자료구조이다.

서로소 집합 자료구조는 서로 다른 원소들이 같은 집합에 속해있는지를 판단하기 위해 사용하는 자료구조이다.
서로소 집합엔 MakeSet, Find, Union 세 가지 연산이 있다.

MakeSet

새로운 집합(parent 배열)을 생성하는 연산

처음 집합을 생성할 때 각 노드는 부모 노드가 없기 때문에 자기 자신을 가르키는 parent 배열을 생성한다.

int n = 10; // 노드의 개수
int[] parent = new int[n];

// 처음 parent 배열을 초기화 할 때는 각 노드가 자기 자신을 가르키도록 설정한다.
for (int i = 0; i < n; i++) {
    parent[i] = i;
}

Find

재귀를 이용해서 node의 root node를 찾는 연산

parent 배열을 이용하여 각 node의 parent node 거슬러 올라가며 root 노드를 찾는다.

7번 노드의 root 노드를 찾는 과정
- 7번의 parent == 6번
- 6번의 parent == 2번
- 2번의 parent == 1번
- 1번의 parent == 1번 -> parent가 자기 자신과 같은 경우 해당 node는 root 노드

public int find(int x) {

    if (parent[x] == x) // 부모 노드 == 자기 자신
        return x;
    else { // 부모 노드가 있다면 부모 노드로 올라감(재귀)
        return find(parent[x]);
    }
}

Union

두 집합(트리)을 하나의 집합으로 합치는 연산

a가 root node인 트리와 e가 root node인 트리를 Union하면 오른쪽 트리가 된다.

아래 사진과 같이 최악의 경우 선형 트리가 되어 Union, Find 연산 모두 O(n)가 될 수 있다.
이러한 문제는 두 트리의 root 노드 중 작은 값을 root로 둠으로써 해결할 수 있다.(Union by Rank)

성능이 향상된 Find & Union

경로 압축(Find)

find 연산을 수행할 때 해당 노드가 root 노드를 가리키도록 하여 결과적으로 find를 수행한 모든 노드가 root 노드를 가리키게 하는 방법

이 방법을 수행하여 모든 노드가 root를 가리키는 평평한 트리를 만든 이후부터는 모든 find 연산의 시간 복잡도가 O(1)이 된다.
아래 사진과 같이 값이 2인 node와 3인 node에 find 연산을 수행하면 평평한 노드가 완성되고 이 이후부터 find 연산은 O(1)의 시간복잡도를 갖게 된다.

public int find(int x) {

    if (parent[x] == x) // 부모 노드 == 자기 자신
        return x;
    else {
        return parent[x] = find(parent[x]);
    }
}

Union by Rank

두 트리를 Union할 때 작은 트리를 큰 트리에 붙이는 방법

즉, 트리의 높이(height)가 작거나 사이즈(size)가 작은 트리를 큰 트리에 붙이는 것을 의미한다.

사용 방법
- rank 배열을 생성하고 index는 노드, value는 해당 노드의 트리 크기(높이 or 사이즈)가 들어간다.

Union by Height

rank 배열의 value 값으로 트리의 size를 넣는 방식

int[] ranks = new int[n];
// rank 배열의 값은 0으로 초기화한다.
for (int i = 0; i < rank.length; i++)
    rank[i] = 0;

public int unionByHeight(int a, int b) {
    a = find(a);
    b = find(b);

    if (ranks[a] < ranks[b]) {
        parent[a] = b; // 랭크가 낮은 트리를 랭크가 높은 트리에 붙임
    } else if (ranks[a] > ranks[b]) {
        parent[b] = a; // 랭크가 낮은 트리를 랭크가 높은 트리에 붙임
    } else { // ranks[a] == ranks[b]
        parent[b] = a;  // 아무거나 붙이고 (여기서는 b를 a에 붙임)
        ranks[a]++;    // a의 랭크를 1 증가
    }
}

Union by Size

rank 배열의 value 값으로 트리의 height를 넣는 방식

int[] ranks = new int[n];
// rank 배열의 값은 0으로 초기화한다.
for (int i = 0; i < rank.length; i++)
    rank[i] = 0;

public int unionByHeight(int a, int b) {
    a = find(a);
    b = find(b);

    if (sizes[a] < sizes[b]) {
        parent[a] = b;
        sizes[b] += sizes[a]; // b의 크기에 a의 크기를 더함
    } else { // sizes[a] >= sizes[b]
        parent[bㄱ] = a;
        sizes[a] += sizes[b]; // a의 크기에 b의 크기를 더함
    }
}

출처

https://yoongrammer.tistory.com/102
https://jh2021.tistory.com/35
https://www.dotnetlovers.com/article/184/disjoint-sets-data-structure
https://velog.io/@mu1616/%EB%B6%84%EB%A6%AC%EC%A7%91%ED%95%A9Disjoint-set