유니온 파인드(Union-Find) 알고리즘

유니온 파인드 알고리즘이란?

간단하게는 합집합을 구하는 알고리즘이다.
여러 노드 중 두 개의 노드를 선택하여 서로 같은 그래프에 속하는지 판별하는(find) 알고리즘이자 연결되어 있다면 같은 부모를 같게끔 합치는(union) 알고리즘이다.

설명

위 그림처럼 모두 연결되어 있지 않다면, 모든 값들의 부모는 각자 자신이라고 한다.

이를 코드로 나타내자면 아래와같다.

parent = IntArray(n){ it }

//or
for(i in 0 until n){
	parent[i] = i
			}

여기서 우리는 union(),find()을 통해 0과1, 1과2를 연결하고 0과 2의 부모가 같은지 확인할 것이다.

먼저 union()으로 두 개의 노드를 각각 합쳐본다면, 아래 그림과 같이 된다.

또 이것을 나열해보면 이렇게 된다.

이후 0과 2의 부모가 같은 지 확인해야하는데, find()메서드를 보면
2의 부모인 1, 1의 부모인 0까지 가기위해 재귀를 사용한다.

전체 코드

private lateinit var parent: IntArray

private fun main() {
    val n = 5
    parent = IntArray(n){it}

    union(0, 1)
    union(1, 2)

    if (isConnected(0, 2)) println("0과 2는 연결되어 있습니다.")
    else println("0과 2는 연결되어있지 않습니다.")
}

// 0과 2의 바로 위의 부모 값은 다르기때문에
// 거슬러 올라가 최종적으로 나오는 부모의 값을 같은지 확인한다.
// 2로 예를 들면, 2의 부모: 1 -> 1의 부모: 0
private fun find(x: Int): Int {
    if (x == parent[x]) return x
    else {
        parent[x] = find(parent[x])
        return parent[x]
    }
}

private fun union(x: Int, y: Int) {
    val parentX = find(x)
    val parentY = find(y)
    // 부모가 같으므로 합칠 게 없음
    if (parentX == parentY) return
    // 부모가 다르므로 x의 부모를 y의 부모가 들어갈 자리에 위치시킴
    else parent[y] = parentX
}

private fun isConnected(x: Int, y: Int) = find(x) == find(y)

관련 문제

백준 - 여행가자

백준 - 집합의 표현

백준 - 공항