[백준/BOJ] 4386번: 별자리 만들기

문제

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

4386번: 별자리 만들기

해설

처음 입력으로 별의 개수와 별의 좌표를 입력받는다.

이번 문제에서는 기본적인 수학의 개념도 필요하다.

두 점 사이의 거리를 구해야하기 때문이다.

두 점 사이의 거리를 구하는 공식은 다음과 같다.

√(x2-x1)² + (y2-y1)²

 

두 별 사이의 거리를 구하는 방법을 알았다면,

별 거 없다는 것을 다들 알 수 있다.

 

이제 크루스칼 알고리즘을 이용하여 최소 비용을 구하면 된다.

이 때 소수점 2째자리까지 출력하는 것에 주의하자.

소스 코드

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

private lateinit var parent: IntArray

data class Info(val start: Int, val end: Int, val distance: Double): Comparable<Info> {
    override fun compareTo(other: Info): Int {
        if(distance > other.distance) return 1
        return -1
    }
}

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()

    parent = IntArray(n + 1)
    repeat(n) { i -> parent[i] = i }

    val arr = Array(n) { Pair(0.0, 0.0) }
    repeat(n) { i ->
        val pos = readLine().split(" ").map { it.toDouble() }
        arr[i] = Pair(pos[0], pos[1])
    }

    val pq = PriorityQueue<Info>()
    for(i in 0 until n) {
        for(j in i + 1 until n){
            val distance = sqrt((arr[j].first - arr[i].first).pow(2) + (arr[j].second - arr[i].second).pow(2))
            pq.add(Info(i, j, distance))
        }
    }

    var ans = 0.0
    var cnt = 0
    while(cnt != n - 1) {
        val cur = pq.poll()
        if(find(cur.start) != find(cur.end)) {
            union(cur.start, cur.end)
            ans += cur.distance
            cnt++
        }
    }

    println(String.format("%.2f", ans))
}

private fun union(a: Int, b: Int) {
    val aParent = find(a)
    val bParent = find(b)

    parent[bParent] = aParent
}

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