서로소 집합 DSU(Disjoint set - Union) / 합집합 찾기 (Union-Find) kotlin

 

Disjoint Set(서로소 집합)

- 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합

서로소 집합

 

DSU(Disjoint Set Union)

-  데이터 구조는 여러개의 서로소 집합(겹치지 않도록) 원소(데이터)를 저장하는 자료구조이다. 

- union–find 또는 merge-find 라고도 부른다.

- 두 서로소 집합을 합쳐 하나의 집합으로 만들 수 있다(union)

-  2개의 서로 다른 원소가 같은 집합인지 "대표원소를 통해" 확인할 수 있다(find)

 

Union

 

구현

예) 총 원소가 0번 원소부터 7번까지 8개의 원소가 있다고 가정하고,

처음에는 자기 자신만을 포함하는 총 8 개의 집합이 있다고 가정해 보자.

배열로 Index는 해당 원소, value는 속한 집합의 "대표원소" 이다.

 

* 대표원소를 결정하는 방법은 다양하다 여기선 집합의 가장 작은 값으로 한다.

여기서 만약 2번 집합과 3번 집합 합쳐지고(union) 5번 집합과 6번 집합 합쳐(union)지면,

union(2, 3) 2-3 집합의 대표는 2

union(5, 6) 5-6 집합의 대표는 5

  더 많은 집합들이 서로 합쳐지면 아래와 같이 표현 할 수 있다. 

union(3, 5)

 

kotlin code

/*
    재귀적으로 해당 idx의 집합 대표값을 찾아서
    변경하고, 반환함.
 */

fun searchParent(n: Int): Int =
    if (arr[n] == n)
        n
    else {
        arr[n] = searchParent(arr[n])
        arr[n]
    }

/*
    각 원소의 대표값을 찾아서 변경하여 하나의 집합으로 표현해준다.
 */
fun union(a: Int, b: Int) {

    val parentA = searchParent(a)
    val parentB = searchParent(b)

    if (parentA < parentB) {
        arr[parentB] = parentA
    } else {
        arr[parentA] = parentB
    }
}

/*
    두 원소가 같은 대표값을 가지는지 확인 한다.
 */
fun find(a: Int, b: Int): Boolean =
    searchParent(a) == searchParent(b)

val arr = Array(10) { it }

fun main() {

    union(1,2)
    union(8,9)

    println(arr.joinToString(" "))
    union(1,8)
    println(arr.joinToString(" "))

    println(find(2,9))
}