프로그래머스 섬 연결하기

class Solution {
    fun solution(n: Int, costs: Array): Int {
        var answer = 0
        val set = IntArray(n)
        for(i in 0 until set.size) {
            set[i] = i //부모 설정
        }
        Arrays.sort(costs) { a, b -> a[2].compareTo(b[2]) } //간선의 비용순으로 정렬
        for (i in 0 until costs.size) {
            if(getParent(set,costs[i][0])!=getParent(set,costs[i][1])) { //같은 부모를 가지고 있는지 체크
                answer+=costs[i][2]
                unionParent(set, costs[i][0], costs[i][1])
            } 
        }
        return answer
    }
    
    fun getParent(set: IntArray, x: Int): Int { //부모를 찾는다

        return if (set[x] == x) x
        else {
            getParent(set, set[x])
        }
    }

    fun unionParent(set: IntArray, a: Int, b: Int) { //더 큰 쪽의 부모로 부모(root)를 합친다.
        val num = getParent(set, a)
        val num2 = getParent(set, b)

        if(num < num2) set[num2] =num
        else set[num] =num2
    }
}

 

크루스칼 알고리즘을 사용한다.

크루스칼 알고리즘은 연결된 간선들의 최소 비용을 구해내는 알고리즘이다.

방법으로는 간선의 비용순으로 정렬한 뒤 정렬된 간선들의 부모를 자기 자신으로 설정한다.

이후 유니온 파인드를 이용하여 연결된 간선의 부모를 정한뒤 사이클이 완성하지 않고 모두 연결하면

최소신장 트리가 완성 된다.

유니온 파인드란 check를 통해 같은 부모를 가지고 있는지 확인하고

부모가 다를 경우 더 작은 값을 가지고 있는(다른 조건 선택 가능) 부모로 합치는 것을 말한다.