[백준 4386번] [Kotlin] 별자리 만들기

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

4386번: 별자리 만들기

 

난이도 : 골드 3
태그 : 그래프 이론, 최소 스패닝 트리

 

 

설명

모든 별을 선으로 이어 별자리를 만드는 문제입니다.

별자리를 잇는다는 건, 두 별을 직선으로 이은 것이며, 모든 별자리는 직/간접적으로 서로 이어져 있어야 합니다.

별을 이을 때 거리만큼의 비용이 들 때, 모든 별을 직/간접적으로 이으면서 그 비용이 최소가 되는 경우를 찾아야 합니다.

 

"모든 별(노드)를 선으로 직/간접적으로 이으면서, 그 비용이 최소가 된다"라는 점에서, 최소 스패닝 트리 문제임을 알 수 있습니다.

최소 스패닝 트리에 대해 잘 모르겠다면 아래 포스팅을 참고해주세요.

https://uknowblog.tistory.com/294

[알고리즘] 최소 스패닝 트리 (MST, Minimum Spanning Tree)

 

 

다행이도 별들은 이차원 평면 위에 놓여져 있습니다.

즉, 두 별을 직선으로 이었을 때 거리는 피타고라스로 쉽게 구할 수 있습니다.

 

다른 최소 스패닝 트리에서는 노드와 연결된 간선도 주어지지만,

이 문제에서는 노드와 그 좌표만 주어질 뿐, 간선의 정보는 주어지지 않습니다.

따라서 저는 그냥 n개의 별 중 2개의 별을 이은 모든 간선을 만들어준 뒤,

크루스칼 알고리즘과 유니온 파인드를 사용해 풀이하였습니다.

 

 

 

 

소스코드

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

data class Node(val from: Int, val to: Int, val weight: Double) : Comparable<Node> {
    override fun compareTo(other: Node): Int {
        return if(this.weight > other.weight) 1 else -1
    }
}

data class Star(var x: Double, var y: Double)

var total = 0.0
lateinit var parent: Array<Int>

fun main() {
    val n = readLine()!!.toInt()
    parent = Array(n + 1) { it }

    val stars = Array<Star>(n) { Star(0.0, 0.0) }

    val pq = PriorityQueue<Node>()

    for (i in 0 until n) {
        val line = readLine()!!.split(" ")
        stars[i].x = line[0].toDouble()
        stars[i].y = line[1].toDouble()

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

    while(pq.isNotEmpty()) {
        val node = pq.poll()

        if (find(node.from) != find(node.to)) {
            total += node.weight
            union(node.from, node.to)
        }
    }

    println(total)
}

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

fun union(x: Int, y: Int) {
    val nx = find(x)
    val ny = find(y)
    if (nx != ny) {
        if(x < y) {
            parent[ny] = nx
        } else {
            parent[nx] = ny
        }
    }
}

 

 

 

후기

별들을 이어 별자리를 만든다는 낭만적인 문제였습니다.