크루스칼 알고리즘 & Union-Find

노드 정점들을 연결하는데 가장 적은 비용으로 연결하려면 어떻게 해야할까?

 

 

 

해당 질문을 해결하기 위한 대표적인 방법은 크루스칼 알고리즘이다.

크루스칼 알고리즘이란, 모든 노드를 지나면서 사이클이 생기지 않고 가장 적은 비용을 가는 경로를 알 수 있다.

 

 

 

이 4개의 그림을 보자.

모두 그래프의 모든 정점을 지난다는 것을 알 수 있으며, 순환고리(사이클이 생기지 않는 연결)이다.

이러한 연결을 신장 트리라고 한다.

 

각 그림들의 가중치 합은 다음과 같다.

3 + 4 + 1 = 8	4 + 3 + 2 = 9
4 + 5 + 2 = 11	3 + 2 + 1 = 6

 

가장 작은 가중치 합을 가진 그림은 우하단의 그래프이며, 이러한 값을 갖는 연결을 최소 신장트리라고 한다.

최소 신장 트리를 구하는 대표적인 방법은 다음과 같다.

1. 프림 알고리즘
2. 크루스칼 알고리즘 (Greedy)

 

크루스칼 알고리즘은 어떻게 그래프의 최소 신장 트리를 구할 수 있을까?

 

 

1. 그래프의 정보들을 가중치 값을 기준으로 정렬시킨다.

다음과 같은 입력이 주어진다고 가정하자.

각 줄마다 3개의 수가 담긴 배열이 주어진다. 총 5개의 배열이 주어진다.

0 3 4

2 3 1

1 2 2

0 1 3

1 3 5

val graph = arrayOf(intArrayOf(0, 3, 4), intArrayOf(2, 3, 1), intArrayOf(1, 2, 2), intArrayOf(0, 1, 3), intArrayOf(1, 3, 5))
Arrays.sort(graph) { o1, o2 -> o1[2] - o2[2] }
graph.forEach { println(it.joinToString(" ")) }

 

이 입력값을 오름차순으로 정렬할 경우, [[2, 3, 1], [1, 2, 2], [0, 1, 3], [0, 3, 4], [1, 3, 5]]

 

 

2. Union-Find 알고리즘을 이용하여 각 노드를 구하고 연결값을 갱신한다.

Union-Find 알고리즘을 사용하기 위해 각 정점의 부모 노드 배열을 선언한다.

이 배열에 앞으로 각 노드가 누구와 연결되는지 값을 갱신할 것이고, 처음은 자기 자신이다.

index	0	1	2	3
parent[index]	0	1	2	3

 

 

2-1. 정렬된 배열의 첫번째 원소 [2, 3, 1]을 확인한다.

2와 3을 비교하면 현재 연결된 정점은 없기에 연결을 시켜준다.

연결시킬때 parent[index] 값이 더 작은 값으로 연결한다.

index	0	1	2	3
parent[index]	0	1	2	2

 

이제 3은 2를 더 상위에, 부모 정점으로 가진다.

연결과 동시에 가중치 값을 더한다.

가중치 합 = 1

 

 

2.2. 두번째 원소인 [1, 2, 2]를 확인한다.

index	0	1	2	3
parent[index]	0	1	1	2

 

가중치 합 = 1 + 2

 

 

2.3. 세번째 원소인 [0, 1, 3]을 확인한다.

index	0	1	2	3
parent[index]	0	0	1	2

 

가중치 합 = 1 + 2 + 3

 

 

2.4. 네번째 원소인 [0, 3, 4]를 확인한다.

index	0	1	2	3
parent[index]	0	0	1	2

 

0과 3을 비교하면 같은 0의 값을 가지게 되므로 이 둘은 이미 연결되어있다고 할 수 있다.

또한 연결되면 사이클이 생기므로 연결시키지 않는다.

가중치 합 = 1 + 2 + 3

 

 

2.5. 다섯번째 원소인 [1, 3, 5]를 확인한다.

index	0	1	2	3
parent[index]	0	0	1	2

 

1의 부모는 0, 3의 부모도 0이므로 둘을 연결하면 2.4처럼 사이클이 생기게 되고, 부모 또한 같기 때문에 연결시키지 않는다.

 

이렇게 연결 가능한 부모노드를 갱신시켜 사이클을 돌지 않는 가장 짧은 가중치의 누적합을 구한다.

가중치 합 = 1 + 2 + 3 = 가장 짧은 경로 = 최소 신장 트리

크루스칼 알고리즘이 구현된다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*

lateinit var parent: IntArray

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val graph = arrayOf(intArrayOf(0, 3, 4), intArrayOf(2, 3, 1), intArrayOf(1, 2, 2), intArrayOf(0, 1, 3), intArrayOf(1, 3, 5))
    // 가중치 값을 기준으로 오름차순 정렬
    Arrays.sort(graph) { o1, o2 -> o1[2] - o2[2] }
    parent = IntArray(graph.size) { it }

    // 가중치 총 합
    var total = 0
    for (node in graph) {
        // 부모 노드를 구하고 부모 노드를 비교
        if (find(node[0]) != find(node[1])) {
            // 부모가 다르다면 두 노드의 연결값을 갱신하며 가중치를 더한다.
            total += node[2]
            union(node[0], node[1])
        }
    }

    bw.write("$total")
    bw.flush()
    bw.close()
}

fun union(x: Int, y: Int) {
    // x, y 각각의 부모 노드를 구한다.
    val nx = find(x)
    val ny = find(y)

    // 부모 노드를 비교해 더 작은 값으로 부모 노드를 갱신한다.
    return if (nx < ny) {
        parent[ny] = nx
    } else {
        parent[nx] = ny
    }
}

// 대표가 그룹의 가장 작은 값이면 해당 값을 반환, 아니면 재귀
fun find(n: Int): Int = if (parent[n] == n) n else find(parent[n])

 

 

관련 문제:

https://small-stepping.tistory.com/818

1414번: 불우이웃돕기

 

https://small-stepping.tistory.com/927

1976번: 여행 가자