[백준/BOJ] 1774번: 우주신과의 교감

문제

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

1774번: 우주신과의 교감

문제

최소 비용을 구해야 하기 때문에, MST 알고리즘을 사용하는 문제이다.

따로 어떤 노드부터 시작해라라는 말이 없으므로 크루스칼 알고리즘을 사용하였다.

 

황선자씨는 이미 교감하고 있는 우주신들이 있다.

따라서 우선적으로 이미 교감하고 있는 우주신들을 union을 통해 합집합 연산을 해준다.

 

이후 아직 연결되지 않은 우주신들과의 거리를 구하여 우선순위 큐에 시작점, 도착점, 거리를 넣어준 후, 거리를 기준으로 오름차순 정렬하여 전형적인 크루스칼 알고리즘을 수행해나가면 된다.

소스 코드

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

private lateinit var parent: IntArray

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

fun main() = with(System.`in`.bufferedReader()) {
    val (godCnt, alreadyConnect) = readLine().split(" ").map { it.toInt() }

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

    val pos = ArrayList<Pair<Double, Double>>()
    repeat(godCnt) {
        val (y, x) = readLine().split(" ").map { it.toDouble() }
        pos.add(Pair(y, x))
    }

    repeat(alreadyConnect) {
        val (start, end) = readLine().split(" ").map { it.toInt() }
        union(start, end)
    }

    val pq = PriorityQueue<EdgeInfo>()
    for(i in 0 until pos.size) {
        for(j in i + 1 until pos.size) {
            val dist = sqrt((pos[j].first - pos[i].first).pow(2) + (pos[j].second - pos[i].second).pow(2))
            pq.add(EdgeInfo(i+1, j+1, dist))
        }
    }

    var ans = 0.0
    while(pq.isNotEmpty()) {
        val cur = pq.poll()
        if(find(cur.start) != find(cur.end)) {
            union(cur.start, cur.end)
            ans += cur.dist
        }
    }

    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] == -1) return -1
    if(parent[i] != i) parent[i] = find(parent[i])
    return parent[i]
}