섬 연결하기

🔒 문제

---

💭 생각의 흐름

"최소 비용으로 모두 통행 가능하도록" ==> Minimum weight
"순서가 바뀌더라도 같은 연결로 봅니다." ==> Undirected graph
==> MST (Minimum Spanning Tree)
👉 Kruskal Algorithm

[Kruskal Algorithm]

Cycle Check를 위한 Union - Find 함수 작성
(1) 모든 Edge의 weight (가중치) 오름차순 정렬
(2) 가중치 적은 Edge부터 차례로 검사하며 Cycle 생성 여부 검사
Cycle exists -> discard it
Cycle not exists -> union it
(3) 모든 Edge (노드 수 - 1) 를 연결할 때 까지 (2) 반복

---

🔑 풀이

class Solution {

    lateinit var parents: IntArray
    lateinit var ranks: IntArray

    // Path compression using recursive function
    private fun findRoot(vertex: Int): Int {
        if (vertex != parents[vertex]) {
            parents[vertex] = findRoot(parents[vertex])
        }
        return parents[vertex]
    }

    // Union By Rank
    private fun unionSet(x: Int, y: Int) {
        val xRoot = findRoot(x)
        val yRoot = findRoot(y)

        if (ranks[xRoot] < ranks[yRoot]) parents[xRoot] = yRoot
        else if (ranks[xRoot] > ranks[yRoot]) parents[yRoot] = xRoot
        else { // same rank -> smaller root has priority!
            if (xRoot <= yRoot) {
                parents[yRoot] = xRoot
                ranks[xRoot]++
            } else {
                parents[xRoot] = yRoot
                ranks[yRoot]++
            }
        }
    }

    private fun isCycle(x: Int, y: Int): Boolean = (findRoot(x) == findRoot(y))


    fun solution(n: Int, costs: Array<IntArray>): Int {
        parents = IntArray(n + 1) { it } // initialize parent(root) it self
        ranks = IntArray(n + 1)

        // sortBy != sortedBy
        // sort weight ascending
        costs.sortBy { it[2] }
        var answer = 0
        var edgeCount = 0

	// The number of edges in Spanning Tree is the number of Vertices - 1 (V-1 == n - 1)
        while (edgeCount < n - 1) {
            for (cost in costs) {
                if (!isCycle(cost[0], cost[1])) {
                    unionSet(cost[0], cost[1])
                    answer += cost[2]
                    edgeCount++
                }
            }
        }
        
        return answer

    }
}

---