[자료구조] 서로소 집합(Disjoint-Set)

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

---

Disjoint-Set은 많은 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조입니다.
Disjoint-Set은 두 가지 연산을 제공합니다.

1. Find 연산: 어떤 원소가 주어졌을 때, 이 원소가 속한 집합을 반환합니다. 집합의 대표(representative)를 반환합니다.
2. Union 연산: 두 개의 집합을 하나의 집합으로 합칩니다.

즉, 두 노드가 같은 그래프에 속하는지 판별하거나, 하나의 그래프로 합칠 때 사용할 수 있습니다.

아래와 같이 어떠한 연결도 없는 8개의 노드가 있다고 가정해보겠습니다.

[그림 1] 각각의 노드들과 자신이 속한 그래프에서의 부모 노드

보통 그래프라 하믄 여러 개의 노드들이 간선으로 연결되어 있는 그림을 떠올리실텐데, 위처럼 노드가 1개여도 그래프입니다.
즉, 위 그림은 현재 노드가 1개뿐인 8개의 그래프로 볼 수 있습니다. 각 그래프들은 현재 자기 자신만을 집합의 원소로 가지고 있죠. 

당연히 각각의 노드는 자기가 속한 그래프의 원소가 자기 자신 밖에 없기 때문에 부모 노드로 자기 자신을 가집니다. 🙂

 

위 그래프에서 union(3, 4); union(7, 8)을 해주어 간선을 추가해보겠습니다.

[그림 2] 그래프에서 간선을 추가해준 뒤 갱신된 노드번호-부모노드 테이블

위 표를 보면 4번 노드의 부모 노드가 3으로 바뀌었고, 8번 노드의 부모 노드가 7로 바뀌었습니다.
저는 Union(합침) 작업을 할 때는 작은 값이 기준이 되도록 했습니다. (부모노드가 되는 기준은 설정하기 나름이라고 생각합니다. 😉 )
다시 위 그래프에 간선을 추가해보겠습니다.

[그림 3] 또 다시 간선을 추가해준 뒤 갱신된 노드번호-부모노드 테이블

규칙이 보이시나요?
같은 그래프 내의 원소들은 동일한 부모노드를 가집니다 ! 😯
즉, 두 노드의 부모 노드가 누군지 찾아보면 두 노드가 같은 그래프에 속하는지 확인할 수 있게 됩니다. (Union-Find에서 Find 부분)

2. 코드

---

C 언어를 이용해서 Disjoint-Set의 두 연산들을 코드로 살펴보겠습니다.

1. union() : 파라미터로 들어온 v2정점을 v1그래프로 합칩니다. (부모노드 값을 변경해주는 것만으로 간단히 해결하고 있습니다.)
2. find() : 입력으로 들어온 정점의 부모 노드를 구합니다.

boolean union(int v1, int v2) {
    v1 = find(v1);
    v2 = find(v2);
    if (v1 != v2) {
        parents[v2] = v1;
        return true;
    }
    return false;
}
int find(int v) {
    if (parents[v] == v) return v;
    return parents[v] = find(parents[v]);
}

위 코드에서 find() 함수를 잠깐 살펴보겠습니다.

return parents[v] = find(..)로 재귀로 부른 가장 끝 부모 노드의 번호를 해당 그래프에 소속된 모든 노드의 부모로 세팅해주고 있습니다.

이를 Path Compression이라고 하는데 그림으로 살펴보면 다음과 같습니다.

[그림 4] Path Compression

위 그림에서 빨간색 테두리는 Find-Set 연산에서 파라미터로 넣은 지점을 표시하였습니다.

Find-Set 연산에서 return find();처럼 써주면 위 그림의 좌측과 같습니다.

Find-Set 연산에서 return parent[v] = find();처럼 써주면 위 그림의 우측과 같습니다.

즉, 그래프에 속한 모든 노드들의 부모노드로 바로 위에 있는 부모노드를 저장해두는 것이 아니라, 가장 끝에 있는 최종적인 부모 노드를 저장합니다. 그렇기 때문에 다음 Find-Set 연산을 할때는 재귀를 1번만 돌리면 부모를 바로 찾을 수 있게 됩니다.

3. 참고자료

---

[1] https://namu.wiki/w/Union Find

[2] https://blog.naver.com/ndb796/221230967614

[3] https://brenden.tistory.com/33