[백준/BOJ] 21924번: 도시 건설

문제

https://www.acmicpc.net/problem/21924

21924번: 도시 건설

해설

최소 신장 트리(MST)에 대해 알고 있다면, 굉장히 쉬운 문제이다.

모든 간선의 비용을 합한 값에서 최소 신장 트리를 구해 그만큼의 비용을 빼주면 된다.

나는 크루스칼 알고리즘을 이용하였다.

 

주의할 점으로는 입력 범위가 크므로 int형을 사용한다면 틀리게 된다.

long을 사용하여야 한다.

소스 코드

import java.util.*

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

private lateinit var parent: IntArray

fun main() = with(System.`in`.bufferedReader()) {
    val (nodeCnt, edgeCnt) = readLine().split(" ").map { it.toInt() }

    parent = IntArray(nodeCnt + 1)
    repeat(nodeCnt) { i -> parent[i] = i }

    val pq = PriorityQueue<Info>()
    var totalCost = 0L
    repeat(edgeCnt) {
        val (start, end, cost) = readLine().split(" ").map { it.toInt() }
        totalCost += cost
        pq.add(Info(start, end, cost))
    }

    var minCost = 0L
    var cnt = 0
    repeat(edgeCnt) {
        val cur = pq.poll()
        if(find(cur.start) != find(cur.end)) {
            union(cur.start, cur.end)
            minCost += cur.cost
            cnt++
        }
    }

    if(cnt != nodeCnt - 1) println(-1)
    else println(totalCost - minCost)
}

private fun union(a: Int, b: Int) {
    val aParent = find(a)
    val bParent = find(b)

    parent[bParent] = aParent
}

private fun find(i: Int): Int {
    if(parent[i] != i) parent[i] = find(parent[i])
    return parent[i]
}