[백준/BOJ] 1197번: 최소 스패닝 트리

문제

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

1197번: 최소 스패닝 트리

해설

최소 신장 트리의 기본적인 문제이다.

크루스칼 알고리즘과 프림 알고리즘으로 해결이 가능한데, 나는 우선 크루스칼 알 고리즘을 이용하여 해결하였다.

크루스칼 알고리즘은 가중치가 가장 작은 간선부터 선택해 나가는 알고리즘이다.

자세한 설명은 아래를 참고하면 된다.

https://jjunsu.tistory.com/221

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

소스 코드

import java.util.*

private lateinit var parent: IntArray

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

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<Element>()
    repeat(edgeCnt) {
        val (start, end, cost) = readLine().split(" ").map { it.toInt() }
        pq.add(Element(start, end, cost))
    }

    var ans = 0
    repeat(edgeCnt) { i ->
        val ele = pq.poll()
        if(find(ele.start) != find(ele.end)) {
            union(ele.start, ele.end)
            ans += ele.cost
        }
    }

    println(ans)
}

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]
}