[알고리즘] Disjoint Set:: 늦깎이 IT

---

이 포스팅은 이전의 [유니온 파인드] 내용을 보완하여 다시 작성된 포스팅입니다.

이 포스팅을 작성하며 Geek과 권오흠 교수님의 강의, [이곳]을 참고하였습니다.

---

[ 디스조인트 셋(Disjoint Set)이란? ]

디스조인트 셋이란 "상호 배타적"인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다.

즉, 교집합이 없는 서로 다른 데이터들로 이루어진 자료구조라고 할 수 있다.

• S = { 1, 2, 3, 4 }라는 전체 집합이 있다고 가정한다. 이때 S의 부분 집합 A = { 1, 2 }와 B = { 3, 4 }는 서로Disjoint Set이라고 한다.

• S의 부분 집합 A와 B의 교집합은 공집합이기 때문이다.

• 반대로, 부분 집합 C = { 1, 2, 3 }과 D = { 1, 2 }는 서로 공통된 원소 { 1, 2 }를 가지고 있기 때문에 Disjoint Set이 아니다.

[ 디스조인트 셋의 연산 ]

• Make-Set(x) : 원소 x에 대하여 독립된 집합을 만든다.

• Find(x) : x가 속한 부분집합의 대표 값(루트 노드)를 반환한다.

• Union(x ,y) : x가 속한 부분 집합과 y가 속한 부분집합을 합친다.

[ Make-Set ]

Make-Set(x) 연산은 최초로 한 번만 수행된다. 아래 그림을 보자.

초기상태에 각 노드들은 다른 집합에 대하여 모두 Disjoint한 상태이므로 자기 자신을 부모노드로 갖는다.

Make-Set 연산의 시간복잡도는 노드의 수를 N개라고 했을 때, 총 N번 수행하므로 O(N)만큼의 시간 복잡도를 갖는다.

[ Find ]

Find(x)는 노드 x의 부모(루트 노드)를 반환하는 연산을 수행한다. 디스조인트 셋에서 같은 임의의 두 노드들이 같은 집합에 속해있는지 확인하는 방법은 각각의 노드들의 부모 노드가 같은지 확인하는 것이다. 

아래 그림을 보자.

• 노드 5의 부모는 1이다.
  

• 노드 4의 부모는 1이다.

• 노드 3의 부모는 1이다.

• 노드 2의 부모는 1이다.

• 노드 1의 부모는 자기자신이다.

노드 1을 부모노드로 갖는 ( 2, 3, 4, 5 ) 노드들은 하나의 집합에 속해있다. 즉, 노드 ( 1, 2, 3, 4, 5 ) 노드들은 모두 하나의 집합에 속해있음을 알 수 있다. 

[JAVA 코드]

public static int find(int[] parent, int u) {
 
    if (u == parent[u])
        return u;
 
    return find(parent, parent[u]);
}

parent 배열에는 각 노드의 부모노드가 저장되어 있다. 노드 u의 부모가 자기 자신이라면 루트 노드이므로 u를 반환하고, 아니라면 자기자신의 부모노드를 찾기위해 재귀적으로 함수를 호출한다. 이 코드를 최적화하는 방법은 아래에서 설명한다.

[ Find 연산의 시간 복잡도 ]

위 그림에서 Find 연산의 시간 복잡도는 어떻게 될까? 트리의 높이를 h라고 했을 때, 시간 복잡도는 O(h)로 나타낼 수 있다. 그 이유는 노드 5가 부모 노드인 1을 찾아가기 위해서는 트리의 높이만큼 거슬러 올라가기 때문이다.

이를 통해서, Find 연산의 시간 복잡도는 트리의 높이에 비례한다는 것을 알 수 있다.

[ Path Compression ]

Find 연산이 트리의 높이에 비례한다는 것은, 트리의 높이가 높을수록 수행시간도 오래 걸린다는 것이다.

그렇기 때문에 트리의 높이를 최소화 시키는 것이 수행시간을 줄일 수 있는 방법이 될 수 있다.

아래 그림을 보자.

• 노드 5의 부모는 1이다.
  

• 노드 4의 부모는 1이다.

• 노드 3의 부모는 1이다.

• 노드 2의 부모는 1이다.

• 노드 1의 부모는 자기자신이다.

이전 그림과의 공통점과 차이점을 찾았는가? 

이전 그림에서 모든 노드들이 같은 부모노드를 가지고 있었음에도 트리의 높이가 4라는 것을 알 수 있다.

하지만 이 그림에서는 모든 노드들이 같은 부모노드를 가지고 있음에도 트리의 높이는 2에 불과하다.

이처럼, Find 연산을 수행하면서 트리의 높이를 낮추는 것을 [ Path Compression ]이라고 한다.

[JAVA 코드]

    public static int findPathCompression(int[] parent, int u) {
 
        if (u == parent[u])
            return u;
        return parent[u] = find(parent, parent[u]);
    }

위의 코드와 달라진 점은, 부모를 찾아가는 과정에서 자기가 속해있는 부모노드의 값을 바꾸는 것이다.

[ Union ]

Find 연산을 통해, 임의의 노드 A와 B의 부모노드를 찾았다면 그 노드들을 합치는 과정, Union 연산을 해야한다.

물론, 노드 A와 B가 이미 같은 집합에 속해 있다면 Union 연산을 수행할 필요가 없다.

위에서 Find 연산이 트리의 높이에 비례한다는 것을 설명했다. 마찬가지로 Union 연산을 수행할 때에도 트리의 높이를 최소화할 수 있다면 보다 더 나은 성능을 발휘할 수 있을 것이다.

아래 그림을 보자.

서로 높이가 다른 트리 p와 q를 Union 연산을 통해 합칠 때, 트리의 높이를 최소화하기 위해서는 어떤 트리쪽으로 합쳐야 할까?

높이가 낮은 트리를 높은 트리로 합친다면, 트리의 높이를 최소화할 수 있음을 쉽게 알 수 있다.

즉, 각각의 트리의 높이를 저장하고 있는 배열을 선언하여 Union 연산을 수행할때마다 높이를 비교하여 연산을 수행한다.

[JAVA 코드]

public static void union(int[] parent, int[] rank, int u, int v) {
 
        int uRoot = find(parent, u);
        int vRoot = find(parent, v);
 
        if (uRoot == vRoot)
            return;
 
        int uRank = rank[uRoot];
        int vRank = rank[vRoot];
 
        if (uRank < vRank)
            parent[uRoot] = vRoot;
        else if (uRank > vRank)
            parent[vRoot] = uRoot;
        else {
            parent[uRoot] = vRoot;
            rank[vRoot] += 1;
        }
        
    }

[ Union 연산의 시간 복잡도 ]

Union 연산의 대상이 되는 노드 u와 v에 대해서 Find 연산을 수행하여 각각의 부모노드인 uRoot와 vRoot를 구했다. 그 이후에 높이가 낮은 트리를 더 높은 트리로 합치는 연산을 진행하는 시간은 O(1)만큼의 시간이 걸린다.

Union 연산의 시간 복잡도는 O(1)이고, 위에서 Find 연산의 시간 복잡도는 O(트리의 높이)라고 했으므로, Disjoint-Set의 시간 복잡도는 O(트리의 높이)라고 해야할 까?

[ 더 생각해보기 ]

우리가 생각해야할 것은 트리의 높이인 h의 값이 어떻게 될 것인지 고민해야 한다.

임의의 노드 A와 B가 있다고 가정하자.  A가 속한 트리의 높이는 1이라고 했을 때, 한 번의 Union 연산을 통해서 A가 속한 트리의 높이가 2로 변했다는 것은 A가 자신보다 높은 트리에 합쳐졌다는 뜻이다.

또한 이를 통해, A의 높이가 1증가했다는 것은 노드의 갯수가 최소 2배 증가했다는 것을 알 수 있다.

즉, 어떤 노드가 몇번의 Union 연산을 통해 높이가 h가 됐다면 노드의 갯수 N은 적어도 2^h보다 많다는 것이다.

트리의 높이 h는 최대 logN이라는 것을 알 수 있고, 이를 통해 Find 연산의 시간 복잡도는 O(logN)이라는 것을 알 수 있다.

더불어, N개의 노드가 있을 때 ,Union-Find 연산을 M번 했을 때의 시간 복잡도는 어떻게 될까? Union-Find 연산은 아래의 수식을 만족함이 증명되었다고 한다.

log*N라는 함수는 N에 몇 번의 log를 취했을 때, 그 값이 1이 나오는지 반환하는 수식이다.

위의 표를 살펴보면 N이 65536일 때 log*N는 4, 2^65536일 때 log*N의 크기는 고작 5임을 알 수 있다.

즉, N의 값이 매우 크더라도 log*N 수식은 아주 작은 값을 반환하기 때문에 거의 선행시간 함수라고 볼 수 있고 이에 따라 O(1)만큼의 시간 복잡도를 가진다고 말할 수 있다.