크루스칼 알고리즘 & Union Find 알고리즘 ( 최소 신장 트리 , Kotlin )

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

위의 질문에 해결하기 위한 대표적인 방법으로 크루스칼 알고리즘을 들 수 있습니다.

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

 

아래에 4개의 그림이 있습니다.

4개의 그림 모두 그래프의 모든 정점을 지납니다. 또한 순환고리 즉 사이클이 생기지 않은 연결들입니다.

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

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

 

왼쪽 위 : 3+4+1 = 8

오른쪽 위 : 4+3+2 = 9

왼쪽 아래 : 4+5+2 = 11

오른쪽 아래 : 3+2+1 = 6

 

가장 적은 가중치의 합을 가진 그림은 오른쪽 아래에 있는 그래프입니다.

가장 작은 값을 갖는 연결을 최소 신장 트리라고 합니다.

 

최소 신장 트리를 구하는 대표적인 방법은 두가지가 있습니다. 

1. 프림 알고리즘

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

 

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

 

1. 먼저, 그래프의 정보들을 가중치 값을 기준으로 정렬시켜야 합니다.

 

입력 :

intArrayOf(0,3,4),
intArrayOf(2,3,1),
intArrayOf(1,2,2),
intArrayOf(0,1,3),
intArrayOf(1,3,5)

 

정렬 후 : [[2, 3, 1], [1, 2, 2], [0, 1, 3], [0, 3, 4], [1, 3, 5]]

 

2. Union Find 알고리즘을 이용하여 각 노드 ( union find 알고리즘을 모르시더라도 일단 읽어보시면 이해가 가실거라 생각합니다. )

 

Union Find 알고리즘을 이용하기 위해 

각 정점의 부모 노드 배열을 선언합니다.

이 배열에 앞으로 각 노드가 누구랑 연결되는지 값을 갱신할 것 입니다.

처음에는 자기 자신을 가집니다.

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

 

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

2와 3을 비교하면 현재 연결된 정점은 없으므로 연결시켜주려 합니다. 

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

 

 

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

 

이제 3은 2를 더 상위에 , 부모 정점으로 가지고 있습니다.

연결하며 동시에 가중치 값을 더합니다.

현재 경로의 합 값 = 1

 

다음 [1, 2, 2] 를 확인합니다.

 

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

 

현재 경로의 합 값 = 1+2

 

그 다음 [0, 1, 3] 

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

 

현재 경로의 합 값 = 1+2+3

 

그 다음 [0, 3, 4]

3은 parent[index] 값이 2를 가집니다. 

2는 1을 가지고 

1은 0을 가집니다.

마지막으로 0은 0을 가집니다.

결국 0과 3을 비교하면 같은 0의 값을 가지므로 둘은 이미 연결되어있습니다. 또한 연결시키게 되면 사이클이 생기게 됩니다. 그러므로 연결시키지 않습니다.

 

현재 경로의 합 값 = 1+2+3

 

마지막으로  [1, 3, 5]

1의 부모는 0이고 3의 부모는 0입니다. 만약 둘을 연결하면 사이클이 생기고 둘은 이미 부모가 같기 때문에 연결시키지 않습니다.

 

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

 

현재 경로의 합 값 = 1+2+3 = 가장 짧은 경로 = 최소 신장 트리 

 

이렇게 크루스칼 알고리즘을 통해 값을 구할 수 있었습니다.

 

아래는 코드입니다.

 

class Solution {
    fun solution(n: Int, costs: Array<IntArray>): Int {
        var answer = 0
        val parent = IntArray(n) { it }
        val sortedCosts = costs.sortedBy { it[2] }
        println(sortedCosts.map { it.toList() })
        // 정렬된 cost 배열을 반복합니다.
        for(node in sortedCosts) {
        	// 부모를 비교합니다.
            if(getParent(parent,node[0]) != getParent(parent,node[1])) {
                println("${node[0]} -> ${node[1]}")
                // 부모가 같지 않으면 둘을 연결 시켜줍니다.
                union(parent,node[0], node[1])
                answer += node[2]
                println(parent.toList())
            }
        }
        println(answer)
        return answer
    }

	// 부모 노드 구하는 함수
    private fun getParent(parent: IntArray, node: Int) : Int {
    	// 더 이상 위로 연결된 노드 없이 최상위 부모 노드일 때
        if(parent[node] == node) return node
        // 재귀함수를 통해 연결된 부모 노드의 위로 계속 타고 올라감
        return getParent(parent, parent[node])
    }

	// union 함수
    private fun union(parent: IntArray, a: Int, b: Int) {
    	// a의 parent 노드를 구합니다.
        val rootA = getParent(parent,a)
        // b의 parent 노드를 구합니다.
        val rootB = getParent(parent,b)
        // 노드의 부모를 비교해 더 정점의 번호가 적은 노드를 부모 노드로 갱신합니다.
        if(rootA < rootB) parent[rootB] = rootA
        else parent[rootA] = rootB
    }
}