Union-Find

Goal

• Union-Find에 대한 이해
• Union-Find 알고리즘을 구현할 수 있다

---

Union-Find란?

Union-Find란, 서로소 집합(Disjoint-Set)을 표현하는 독특한 자료구조이다.

(Union, Find라는 연산을 포함하기 때문에 Union-Find(합집합 찾기)라는 이름이 붙었다)

 

*Disjoint Set :  서로소 집합을 다루는 자료구조

Union-Find의 연산

union-find에는 다음과 같은 연산을 제공한다.

• make-set(x) : x를 유일한 원소로 하는 새로운 집합을 만든다. => 초기화
• union(x, y) : x가 속한 셋과 y가 속한 집합을 합친다
• find(x) : x가 속한 집합을 찾는다 (집합을 반환, 또는 집합을 대표하는 대푯값(트리의 루트 등)을 반환)

집합 구현은 비트 벡터, 배열, 연결 리스트를 사용해서 구현될 수 있지만, 가장 효율적인 방법은 트리이다.

하나의 트리를 하나의 집합으로 나타낼 수 있고, 그 트리의 루트 노드는 집합을 나타내는 대푯값이다.

 

시간복잡도 계산

find : O(h)

• 트리의 부모 노드까지 거슬러 올라가야 하므로 트리 높이에 비례한다.

union : O(1)

• 한쪽 트리가 다른 한쪽 트리의 서브 트리가 되면 되기 때문에 O(1)만큼의 시간 복잡도를 갖는다.
• 하지만, 각각의 트리의 루트 노드를 찾아야 하기 때문에 find연산이 전체 수행시간의 대부분을 차지한다.

 

Union-Find 사용 예시

• make-set : 초기화. => 모든 노드들이 각각 개별 집합이 되도록 초기화. (자신을 루트로하는 개별적인 트리 형태)
• find(x) : x가 속한 트리(집합)의 루트 노드를 찾는 과정. ex) find(x) == find(y)이면, 두 노드는 같은 집합에 속
• union(x,y) : 두 트리를 합치는(union)과정
  1. find(x), find(y)를 통해 두 노드가 속한 집합을 구한다.
  2. find(x) == find(y) 라면 두 노드가 속한 집합이 같으므로 합칠 필요가 없다.
  3. find(x) != find(y() 라면 두 노드가 속한 집합이 다르므로 합친다. (한쪽 노드의 부모 노드만 변경하면 됨) 

위 과정에서 find 연산의 성능은 트리 높이에 영향을 받으므로,

합칠 때, height값이 작은 쪽이 큰 쪽으로 합쳐지면 find 연산을 좀 더 효율적으로 할 수 있다.

 

Union-Find의 구현

const int MAX_SIZE = 100001;
int parent[MAX_SIZE];

void make_set()
{
    for (size_t i = 0; i < MAX_SIZE; i++)
    {
        parent[i] = i; // 초기화. root노드인 경우 parent를 자기 자신으로 초기화(계산의 편의성을 위해 세팅)
    }
}

int find(int x)
{
    if (x == parent[x]) // 루트 노드인 경우
    {
        return x;
    }

    return find(parent[x]); // 최상위 부모 노드를 찾아서 리턴
}

void unite(int x, int y)
{
    // 각 원소가 속한 트리의 루트 노드를 찾는다
    x = find(x);
    y = find(y);

    parent[y] = x; // y가 속한 트리를 x가 속한 트리의 subtree로 합친다.
}

 

Union-Find를 위와 같이 구현하면 다음 그림과 같은 최악에 상항에서 나쁜 성능을 보일 수 있다.

위와 같은 Skewed Tree의 경우 최악의 상황에서는 find연산이 선형적인 시간복잡도를 갖게된다. (최악의 경우 O(N))

그래서 좀 더 최적화 할 수있는 방법이 필요하다.

 

Union-Find 연산의 최적화 방법

1. 경로 압축(Path Compression) => find 연산시 수행되는 방법
2. union-by-height(=union-by-rank) => union 연산시 수행되는 방법
3. union-by-size => union 연산시 수행되는 방법

참고)

위 두가지 방법을 동시에 수행하면 경로 압축에 의해 트리의 height값이 변경 될 수 있으므로 union-by-height에서 계산한 height값이 정확한 값이 아닐수도 있다.

 

경로 압축(Path Comporession)

find연산을 할 때 수행되는 과정으로, 루트 노드와의 경로를 압축하는 과정이다.

 

find(x)를 하면, x와 루트 노드 경로사이에 존재하는 모든 노드가 자신의 부모 노드로 루트 노드를 가리키게 된다.

 

다음 그림에서 find(0)을 할 경우, 노드(0)과 루트 노드(5) 사이에 존재하는 노드{0, 2, 3, 4}는 모두 자신의 부모 노드로 루트노드(5)를 가리키게 된다. => 경로 압축. (루트와의 경로 길이가 1로 변경)

 

경로를 압축하는 find 함수를 코드로 구현하면 다음과 같다.

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

    return parent[x] = find(parent[x]); // 경로 압축 => 자신의 부모 노드로 루트 노드를 가리키게됨
}

 

시간 복잡도 : O(h)

 

union-by-height

union 연산을 수행할 때 수행되는 과정으로, 상대적으로 높이가 더 작은 트리가 큰 트리 쪽으로 합쳐지는 방법이다.

 

합쳐진 트리의 높이는 기존 두 트리의 최대 높이 값과 같거나 1 더크다. (높이가 같은 경우 기존 높이보다 1 커짐)

• 두 트리의 최대 높이가 다른 경우 높이 : max(x,y)
• 두 트리의 최대 높이가 같은 경우 높이 : max(x,y) + 1

코드 구현

void unite(int x, int y)
{
    // 각 원소가 속한 트리의 루트 노드를 찾는다
    x = find(x);
    y = find(y);

    if (x == y) // 같은 트리에 있다면 합치지 않는다.
    {
        return;
    }

    if (height[x] < height[y])
    {
        parent[x] = y; // x -> y로 합침
    }
    else
    {
        parent[y] = x; //y -> x로 합침
        if (height[x] == height[y]) // 높이가 같았을 경우 최대 높이가 1 증가한다.
        {
            height[x]++;
        }
    }
}

union-by-height연산을 하면 트리의 높이가 증가되는 값을 줄일 수 있지만, 높이를 저장할 추가공간이 필요하다는 단점이 있다.

 

union-by-size

union 연산을 수행할 때 수행되는 과정으로, 상대적으로 size가 더 작은 트리가 큰 트리 쪽으로 합쳐지는 방법이다.

*size : 트리 노드의 개수

 

구현 코드

const int MAX_SIZE = 100001;
int parent[MAX_SIZE];
int nodeCount[MAX_SIZE];

void make_set()
{
    for (size_t i = 0; i < MAX_SIZE; i++)
    {
        parent[i] = i;
        nodeCount[i] = 1;
    }
}

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

    return parent[x] = find(parent[x]);
}

void unite(int x, int y)
{
    x = find(x);
    y = find(y);

    if (x == y) return;
    else if (nodeCount[y] < nodeCount[x])
    {
        parent[y] = x;
        nodeCount[x] += nodeCount[y]; // x의 node 수에 y의 node 수를 더한다.
    }
    else
    {
        parent[x] = y;
        nodeCount[y] += nodeCount[x]; // y의 node 수에 x의 node 수를 더한다.
    }
}

---

References

gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

bowbowbow.tistory.com/26

https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/UnionFind.pdf