[알고리즘] 유니온 파인드(Union-Find) 자료구조

 

 

 

 

 

 

🧐 유니온 파인드 자료구조

유니온 파인드 자료구조(또는 서로소 집합(disjoint set) 자료구조)는 다음 두 종류의 연산을 지원하는 자료구조입니다.

Union : 두 개의 노드가 포함된 집합을 하나의 집합으로 합치는 연산

Find : 특정 노드가 속한 집합의 루트 노드를 반환하는 연산

 

 

 

우선 동빈나님의 설명이 굉장히 좋기 때문에, 동빈나님의 유튜브 링크를 걸어두도록 하겠습니다.

( 저는 그냥 제가 공부하려고 글 쓴 거니까, 유튜브 보러 가세여..ㅠㅠ )

 

 

 

 

 

 

 

 

 

 

 

 

⭐️ Find 연산

Find 연산은 다음과 같은 알고리즘을 통해 구현할 수 있습니다.

1. 해당 노드의 부모 노드와 해당 노드를 비교합니다. 이때 두 노드가 같은 경우, 해당 노드는 루트 노드입니다.

2. 만약 같지 않다면 해당 노드의 부모 노드에 대하여 find 연산을 재귀적으로 호출합니다.

 

 

수도코드는 다음과 같습니다.

find(x) {
    if (x == x.parent) { // 루트 노드인 경우
    	return x
    }
    return find(x.parent); // 부모에 대해 재귀적으로 find 호출
}

 

 

 

 

 

 

 

 

 

 

 

⭐️ Union 연산

Union 연산은 다음과 같은 알고리즘으로 구현할 수 있습니다.

 

1. 두 노드에 대해 Find 연산을 각각 수행하여, 두 노드가 각각 속한 집합의 루트 노드를 찾아냅니다.

2. 두 루트 노드의 Rank를 비교한 뒤 Rank가 작은 루트 노드의 부모를,  Rank가 큰 루트 노드로 설정합니다.

이때, 두 루트 노드의 Rank가 같은 경우 어떤 식으로 합쳐져도 상관없으나, 합쳐진 이후 루트노드의 Rank를 1 올려주는 작업이 필요합니다.

 

 

수도코드는 다음과 같습니다.

union(x, y) {

    xRoot = find(x)
    yRoot = find(y)
    
  	// x가 속한 집합의 Root node의 Rank가 더 높은 경우
    if (xRoot.rank > yRoot.rank) {
    	
        // y가 속한 집합을 x가 속한 집합의 하위 집합으로 포함시키기
        yRoot.parent = xRoot
    }
    
    // y가 속한 집합의 Root node의 Rank가 더 높은 경우 || Rank가 동일한 경우
    else {
    	
    	xRoot.parent = yRoot
        
        // 두 Rank가 동일한 경우 yRoot의 Rank를 1 올려주어야 함
        if (xRoot.rank == yRoot.rank) {
        	yRoot.rank ++
        }
    }
}

 

 

 

 

 

 

 

 

 

 

⭐️ 실제 구현

저는 코틀린으로 구현했습니다.

class UnionFind {
    
    /**
     * Root Vertex 반환
     */
    fun find(vertex: Vertex): Vertex {

        if (vertex == vertex.parent) {
            return vertex
        }

        return find(vertex.parent)
    }
    

    fun union(
        x: Vertex,
        y: Vertex,
    ) {

        val xRoot = find(x)
        val yRoot = find(y)

        if (xRoot.rank > yRoot.rank) {
            yRoot.parent = xRoot
        }
        else {
            xRoot.parent = yRoot

            if (xRoot.rank == yRoot.rank) {
                yRoot.rank += 1
            }
        }

    }
}

class Vertex(
    val value: String,
) {
    var rank: Int = 1
    var parent: Vertex = this
}

 

 

 

 

 

 

 

 

 

 

🧐 유니온 파인드 자료구조의 특징

 

 

 

 

⭐️ Property 1

각 set에 해당하는 tree에서 어떠한 node도 해당 node의 parent 보다 rank가 작습니다.

 

 

⭐️ Property 2

각 set에 해당하는 tree에서 rank가 k인 root node는 최소 $2^k$ 개의 node를 descendeant로 가지고 있습니다.

 

증명은 귀납법을 사용하며 다음과 같습니다.

우선 k = 0 인 경우, rank가 0인 root node는 1개의 node만을 가지므로 성립합니다.

임의의 k에 대하여  rank가 k인 root node는 최소 $2^k$ 개의 node를 descendeant로 가지고 있다고 하겠습니다.

rank가 k인 root node 2개를 union 하는 경우, rank는 1 증가하며, 한 쪽의 root node의 parent가 다른 쪽의 root node로 설정됩니다.

union 결과로 합쳐진 set에 해당하는 tree의 root node의 rank는 k + 1입니다.
이때 합쳐진 set에 해당하는 tree의 노드의 개수를 $n_u$ 라 하고,
합쳐지기 전 rank k인 두 root node가 포함된 tree의 노드의 개수를 각각 $n_1, n_2$ 라 하겠습니다.

가정에 의해 $n_1 \geq 2^k$ 이며 $n_2 \geq 2^k$ 이므로
$n_u = n_1 + n_2 \geq  2^k +  2^k =  2^{k+1}$ 입니다.

따라서 모든 k에 대해 위 속성이 성립합니다.

 

 

 

 

 

⭐️ Property 3

각 set에 해당하는 tree에서 rank가 k인 node는 최대 $\frac{n}{2^k}$ 개 입니다.

 

 

 

 

 

 

 

 

 

 

🧐 경로 압축 (Path compression)

위에서 살펴본 Find 알고리즘은, Union 연산이 편향되게 이루어지는 경우 비효율적으로 동작합니다.

 

최악의 경우 Find 함수는 모든 노드를 다 확인하게 되어 시간 복잡도가 $O(n)$ (n은 Vertex의 개수)이 되어버립니다.

 

이러한 문제점을 해결하기 위해, Find 함수를 최적화하기 위한 경로 압축에 대해 알아보도록 하겠습니다.

 

경로 압축은 다음과 같이 이루어집니다.

 

Find 함수를 재귀적으로 호출한 뒤, parent 값을 Find 함수의 결과로 갱신합니다

 

위 방법을 통해 find를 하며 지나치는 모든 node들에 대하여, 해당 Set의 루트노드의 자식(Child) 노드로 만들어 줄 수 있습니다.

 

 

수도코드는 다음과 같습니다.

find(x) {
    if (x != x.parent) { // 루트 노드가 아닌 경우
    	x.parent = find(x.parent) // 루트 노드의 자식 노드로 트리 구조 변경
    }
    return x.parent
}

 

 

 

 

 

실제 구현은 다음과 같습니다.

fun find(vertex: Vertex): Vertex {

    if (vertex != vertex.parent) {
        vertex.parent = find(vertex.parent)
    }

    return vertex.parent
}

 

 

 

 

 

 

 

최소 신장 트리(MST)를 구하는 데 사용되는 크루스칼 알고리즘을 유니온 파인드 자료구조를 사용하여 구현할 수 있으며,

곧 살펴보도록 하겠습니다 :)

 

 

 

 

 

 

 

 

 

 

⭐️ 연습문제

아래 문제는 백준에 있는 유니온 파인드 기본 문제입니다. 

한번 해보세용 :))

 

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

1717번: 집합의 표현