[백준 16398] - 행성연결(Kotlin)[골드4]

문제

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

16398번: 행성 연결

 

문제 풀이

앞에서 풀었던 1197 최소 스패닝 트리에서 입력형식만 바뀐 거지 문제 풀이는 똑같다.

 

앞선 문제에서 주어졌던 입력 형식인 from->to->value가

배열 형식으로 i -> j -> input값으로 바뀐것이다.

 

따라서 해당 입력형식에 따라 노드를 생성하고, 크루스칼 알고리즘을 사용하면 쉽게 풀 수 있다.

 

전체 코드

package MST.`16398_행성_연결`.LJH

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.PriorityQueue
import java.util.StringTokenizer

class `16398` {

    private val br = BufferedReader(InputStreamReader(System.`in`))
    data class Node(val from: Int, val to: Int, val value: Int)
    private val pq = PriorityQueue<Node>(compareBy { +it.value })
    lateinit var parent: Array<Int>

    init {
        input()
        print(makeMst())
    }

    private fun input() {
        val n = br.readLine().toInt()
        parent = Array(n + 1) { it }
        for (i in 0 until n) {
            val line = br.readLine().split(" ")
            for (j in i+1 until n) {
                pq.add(Node(i, j, line[j].toInt()))
            }
        }
    }

    private fun makeMst(): Long {
        var sum = 0L
        while (pq.isNotEmpty()) {
            val edge = pq.poll()
            if (find(edge.from) != find(edge.to)) {
                sum += edge.value
                union(edge)
            }
        }
        return sum
    }

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

    private fun union(edge: Node) {
        val fromParent = find(edge.from)
        val toParent = find(edge.to)
        if (fromParent > toParent) parent[fromParent] = parent[toParent]
        else parent[toParent] = parent[fromParent]

    }
}

fun main() {
    val solution = `16398`()
}