[백준/BOJ] 1922번: 네트워크 연결

문제

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

1922번: 네트워크 연결

해설

최소 비용을 구하는 문제로 최소 신장 트리를 이용하면 된다.

최소 신장 트리를 구현하는 방법으로는 크루스칼 알고리즘과 프림 알고리즘이 있는데,

나는 이 중 크루스칼 알고리즘을 이용하여 문제를 해결하였다.

 

크루스칼 알고리즘에 대해서는 밑의 글을 확인해보는 것을 추천한다.

https://jjunsu.tistory.com/221

[알고리즘] 크루스칼 알고리즘(Kruscal Algorithm)

결론적으로, 크루스칼 알고리즘을 이용하여 가장 작은 비용으로 모든 컴퓨터를 연결하면 되는 문제이다.

소스 코드

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 computerCnt = readLine().toInt()
    val edgeCnt = readLine().toInt()

    parent = IntArray(computerCnt + 1)
    for(i in 1 .. computerCnt) parent[i] = i

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

    var minCost = 0
    for(i in 0 until edgeCnt) {
        val info: Info = pq.poll()
        if(find(info.start) != find(info.end)) {
            union(info.start, info.end)
            minCost += info.cost
        }
    }

    println(minCost)
}

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

    if(aParent != bParent) {
        parent[bParent] = aParent
    }
}

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