[백준] 6479번: 전력난 - Kotlin[코틀린]

문제

 

6497번: 전력난

 

---

풀이

 

 최소 스패닝 트리를 구하는 문제로 프림과 크루스칼 알고리즘을 이용해 풀이할 수 있다. 이번 문제에서는 크루스칼 알고리즘을 사용하였다.

 

 문제는 최대로 절약할 수 있는 비용을 찾는 것이므로, 크루스칼 알고리즘으로 찾음 최소 스패닝 트리(MST)의 비용을 초기 비용에서 빼준 값을 출력하면 된다.

 

 기본적인 유니온 파인드로는 시간 초과 문제가 발생하여 경로 압축을 적용한 유니온 파인드 구현이 필요하다. 경로압축은 파인드 함수에서 부모를 찾아가는 중간에 거치는 모든 노드들의 부모를 최종적인 루트 노드로 갱신해주는 것으로, 이를 통해 성능을 향상시킬 수 있다.

 

---

코드

 

import java.util.*

data class Edge(val start: Int, val end: Int, val value: Int): Comparable<Edge> {
    override fun compareTo(other: Edge): Int = value.compareTo(other.value)
}

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val sb = StringBuilder()

    while (true) {
        val st = StringTokenizer(br.readLine())
        val vertices = st.nextToken().toInt()
        val edges = st.nextToken().toInt()

        // 입력이 0 0이면 종료
        if (vertices == 0 && edges == 0) break

        var cost = 0
        val graph = ArrayList<Edge>()
        
        // 간선 정보 입력 및 초기 비용 계산
        repeat(edges) {
            with(StringTokenizer(br.readLine())) {
                graph.add(Edge(nextToken().toInt(), nextToken().toInt(), nextToken().toInt()))
            }
            cost += graph[it].value
        }
        
        // 간선을 가중치 순으로 정렬
        graph.sort()

        val parent = IntArray(vertices) { it }
        fun find(a: Int): Int {
            if (parent[a] != a) {
                parent[a] = find(parent[a])
            }
            return parent[a]
        }
        fun union(a: Int, b: Int) {
            val x = find(a)
            val y = find(b)
            if (x != y) {
                parent[y] = x
            }
        }

        // 크루스칼 알고리즘
        fun kruskal(): Long {
            var ans = 0L

            for (edge in graph) {
                if (find(edge.start) != find(edge.end)) {
                    ans += edge.value
                    union(edge.start, edge.end)
                }
            }

            return ans
        }

        // 결과 출력
        sb.append("${cost - kruskal()}\n")
    }

    bw.write("$sb")
    bw.flush()
    bw.close()
    br.close()
}