[kotlin] 별자리 만들기

별자리 만들기 문제 및 입출력 

풀이 접근 

별자리를 잇는다? -> 그래프 형식으로 나오겠구나 ?

선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용 

-> 최소신장트리(MST)를 구축하면 되겠구나? 

풀이 코드  

package com.chanhue.algorithm.백준.골드

import java.util.PriorityQueue
import kotlin.math.sqrt


fun main() {


    val n = readLine()!!.toInt()


    val node = mutableListOf<Pair<Double, Double>>()

    repeat(n) {
        val (x, y) = readLine()!!.split(" ").map { it.toDouble() }
        node.add(Pair(x, y))

    }
    val pq = PriorityQueue<Pair<Double, Int>>(compareBy { it.first })

    val graph = Array(n + 1) { mutableListOf<Pair<Double, Int>>() }

    val visited = BooleanArray(n+1)

    for (i in 0 until n) {
        for (j in i + 1 until n) {
            val dx = node[i].first - node[j].first
            val dy = node[i].second - node[j].second
            val distance = sqrt((dx * dx) + (dy * dy)) // 가중치 계산
            graph[i].add(Pair(distance, j))
            graph[j].add(Pair(distance,i))
        }
    }
    pq.add(Pair(0.0, 0))
    var sum = 0.0

    while (pq.isNotEmpty()) {
        val (cost, vertex) = pq.poll()
        if (visited[vertex] != true) { //방문하지 않은 노드라면
            visited[vertex] = true //방문노드로 바꾸고
            sum = sum + cost
            for ((edgeCost, next) in graph[vertex]) { // 정점을 기준으로 연결되어 있는 애들 추가
                if (visited[next] != true) {
                    pq.add(Pair(edgeCost, next))
                }
            }
        }

    }
    println(String.format("%.2f", sum)) // 소수점 둘째 자리까지 출력

}