4386번: 별자리 만들기 - Kotlin (최소 스패닝 트리)

4386번: 별자리 만들기

문제

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

입력

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

 

 

나의 풀이

이 문제는 최소 스패닝 트리 문제이다. 최소 스패닝 트리에 대한 이해가 있거나 이전에 해결 해봤다면 생각보다 쉽게 해결할 수 있는 문제이다.

원래라면 시작 노드와 출발노드, 가중치 이렇게 3개가 보통 주어지는데 이 문제는 점의 위치가 좌표로 주어지게 된다. 그래서 우리가 할 것은 시작 노드와 출발노드, 가중치를 정해주면 된다. 시작 노드와 출발 노드는 반복문으로 넣어주면 되고 가중치는 좌표의 두 점의 거리를 구하는 공식을 사용하여 넣어주면 된다. 점화식은 다음과 같다.

 

d = √((x₂ - x₁)² + (y₂ - y₁)²)

 

만약 최소 스패닝 트리에 대해 잘 모른다면 아래의 게시글로 가서 해당 문제를 먼저 해결해보길 바란다

 

 

1197번: 최소 스패닝 트리 - Kotlin (크루스칼)

 

 

 

import java.lang.Math.pow
import java.util.*
import kotlin.math.*

data class Node(val from: Int, val to: Int, val weight: Double): Comparable<Node>{
    override fun compareTo(other:Node): Int =
        weight.compareTo(other.weight)
}

lateinit var graph: Array<Int>

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val stars = Array(n) { readLine().split(" ").map { it.toDouble() } }

    val pq = PriorityQueue<Node>()

    for (i in 0 until n) {
        for (j in i + 1 until n) {
            val x = (stars[j][0] - stars[i][0]).pow(2)
            val y = (stars[j][1] - stars[i][1]).pow(2)
            val weight = roundDigit(sqrt(x + y))
            pq.add(Node(i, j, weight))
        }
    }

    graph = Array(n + 1) { it }

    var ans = 0.0

    while (pq.isNotEmpty()) {
        val now = pq.poll()
        if (union(now.from, now.to))
            ans += now.weight
    }

    println(ans)
}

fun roundDigit(number : Double): Double {
    return Math.round(number * Math.pow(10.0, 2.0)) / Math.pow(10.0, 2.0)
}

fun find(x: Int): Int {
    return if (x != graph[x]) {
        graph[x] = find(graph[x])
        return graph[x]
    } else x
}

fun union(x: Int, y: Int): Boolean {
    val tempX = find(x)
    val tempY = find(y)

    return if (tempX != tempY) {
        graph[tempX] = tempY
        true
    } else false
}