서로소 집합은 공통되는 부분이 없는 집합을 말한다.
알고리즘에서는 같은 그룹에 속해있는지 확인하는 경우에 사용할 수 있다.

같은 그룹에 속해있는지 확인하기 위해서 우선 트리를 구성하게 된다.
해당 트리에서 같은 루트를 가진다면 같은 그룹이고 다른 루트를 가진다면 다른 그룹에 속한다.
배열의 초기값으로 자기 자신을 설정한다, 자신의 그룹의 루트는 자신인 것이다.
나중에 두 그룹을 합치는 union 연산을 하게 된다면 그룹의 루트가 자신이 아닌 다른 그룹을 가리키게 된다면 서로 다른 루트를 가지던 두 그룹이 한 루트를 가리키게 되고, 두 그룹이 한 그룹이 된다.

여기에서 문제가 발생한다. 트리를 구성하면서 기울어지게 되면 루트를 찾으러 가게되는 깊이가 증가되서 성능의 하락이 이루어 진다. 그렇기 때문에 깊이압축을 통해서 트리의 높이를 줄이 도록 해야한다.
이를 위해서 부모를 찾는 연산에서 자신의 부모가 루트가 아니면 자신의 부로를 루트로 바꾸어 주면 높이를 낮은 상태로 유지 할 수 있다.

아래는 완성된 코드이다

완성코드

일반 버전

val set = IntArray(n + 1) { it }
fun findSet(idx:Int) :Int{
    if (set[idx] != idx) // 자신이 루트 가 아니면
        set[idx] = findSet(set[idx]) // 자신의 부모를 부모의 부모로 변경 (압축)

    return set[idx]
}

fun unionSet(from:Int, to:Int){
    set[findSet(from)] = findSet(to)// 나의 루트를 다른 집합의 루트로 변경
}

일반적인 코테에서 코드의 길이가 길어지지 않는 다면 main 함수 내부에서 findSet, unionSet 두가지 함수를 구현하고 사용할 수 있다. 간단하게 사용하기 좋은 버전이다.

클래스 버전

private class Set(size: Int) {
    val parents = Array(size) { it }

    fun findSet(p: Int): Int {
        if (p != parents[p])
            parents[p] = findSet(parents[p])
        return parents[p]
    }

    fun union(a: Int, b: Int) {
        val pa = findSet(a)
        val pb = findSet(b)
        data[pa] = pb
    }
}

코드의 길이가 전체적으로 길어지게 된다면 main 함수 내부의 정리가 필요한 경우가 있다. 그렇기에 클래스로 분리하여 구현하는 것도 해볼만하다.