[백준] 1647번: 도시 분할 계획 - Kotlin[코틀린]

문제

 

1647번: 도시 분할 계획

 

---

풀이

 

 이 문제는 MST(최소 스패닝 트리)를 구하는 것로 이번에는 크루스칼 알고리즘을 사용해서 풀이했다.

 

 우선순위 큐를 활용하여 비용이 낮은 순서대로 길을 선택하여 MST를 만들고 사이클이 발생하는 간선은 제외해준다. MST를 만드는 과정에서 발생하는 비용들은 더해준다.

 

 MST에서 간선을 하나 지우는 것으로 마을을 두 개로 나눌 수 있다. 우선 순위 큐를 이용해 MST를 구했기 때문에 가장 마지막에 연결된 간선을 지워주면 된다.

 

---

코드

 

import java.util.PriorityQueue

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

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

    val (house, road) = br.readLine().split(' ').map { it.toInt() }
    val queue = PriorityQueue<Edge>()
    repeat(road) {
        val (start, end, cost) = br.readLine().split(' ').map { it.toInt() }
        queue.add(Edge(start, end, cost))
    }

    val parent = IntArray(house+1){ it }
    fun find(a: Int): Int {
        return if(parent[a] == a) a
        else {
            parent[a] = find(parent[a])
            parent[a]
        }
    }
    fun union(a: Int, b: Int): Boolean {
        val x = find(a)
        val y = find(b)
        return if(x == y) false
        else {
            if(x < y) parent[y] = x
            else parent[x] = y
            true
        }
    }

    var sum = 0
    var max = 0
    while (queue.isNotEmpty()) {
        val next = queue.poll()
        if(union(next.start, next.end)) { // 사이클이 발생하는 간선은 제외
            sum += next.cost
            max = next.cost
        }
    }

    bw.write("${sum - max}")
    bw.flush()
    bw.close()
    br.close()
}