유니온 파인드

유니온 파인드

집합을 표현하기 위한 알고리즘, 특정 원소가 어느 집합에 포함되는지 판단할 때 사용한다. 트리 구조를 응용하여 집합을 표현한다. 루트 노드는 자기 자신을 가리키며 서브 노드는 상위 노드를 가리킨다.

서브트리가 길어질 수록 트리의 루트를 찾는데 시간이 오래걸려 최악의 경우 $O(N)$의 시간이 걸린다. 이를 단축하기 위해 경로압축을 사용할 수 있다. 경로 압축은 모든 서브 노드가 루트를 가리킴으로서 탐색 경로를 최적화한다.

함수는 합치기(unify)와 찾기(find)를 구현하면 된다.

구현

클래스를 활용한 구현

class UnionFind(private val arr: Array<Int>) {
    fun isSameGroup(v1: Int, v2: Int): Boolean {
        return find(v1) == find(v2)
    }

    fun unify(v1: Int, v2: Int) {
        arr[find(v2)] = find(v1)
    }

    private fun find(v: Int): Int {
        if (arr[v] == v)
            return v
        arr[v] = find(arr[v])
        return arr[v]
    }
}

함수를 활용한 구현

val parent = IntArray(v + 1) { it }
fun getAncestor(vertex: Int): Int {
    if (vertex == parent[vertex]) return vertex

    parent[vertex] = getAncestor(parent[vertex])
    return parent[vertex]
}

fun union(a: Int, b: Int) {
    parent[getAncestor(a)] = getAncestor(b)
}