BOJ 16398_행성연결

문제

문제를 보고 최소신장트리 유형인 것은 알았으나 알고리즘이 떠오르지 않아 관련 내용을 다시 학습 후 구현했다.

풀이

package solve_16398

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }

    val n = input()

    val edgeList = ArrayList<Edge>(n*n)

    for(i in 0 until n){
        for (j in 0 until n){
            edgeList.add(Edge(i,j,input()))
        }
    }

    val parent = IntArray(n + 1) { it }
    fun findRoot(node: Int): Int {
        if (parent[node] == node) return node
        parent[node] = findRoot(parent[node])
        return parent[node]
    }

    fun isUnion(a: Int, b: Int): Boolean {
        return findRoot(a) == findRoot(b)
    }

    fun makeUnion(a: Int, b: Int) {
        val r1 = findRoot(a)
        val r2 = findRoot(b)
        if (r1 > r2) parent[r1] = r2
        else parent[r2] = r1
    }

    fun kruskal(){
        edgeList.sortWith { a, b -> a.distance.compareTo(b.distance) }
        var sum = 0L
        for (i in edgeList.indices) {
            val (s, e, d) = edgeList[i]
            if (isUnion(s, e).not()) {
                makeUnion(s, e)
                sum += d
            }
        }
        println(sum)
    }
    kruskal()
}

private data class Edge(val start: Int, val end: Int, val distance: Int)

사용 알고리즘

크루스칼알고리즘을 사용했다.
우선 입력된 간선들을 정렬한 후 작은 것부터 하나씩 확인한다.

이후 간선으로 연결된 두 노드의 뿌리(root 노드)를 확인하여 서로 다른 집합에 연결되어 있다면 하나로 합치고 parent를 같게 만들어 준다.

모든 간선에 대해 정렬된 순서대로 확인하며 같은 집합에 속해있다면 무시한다.