[백준/BOJ] 16398번: 행성 연결

문제

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

16398번: 행성 연결

해설

최소 신장 트리를 이용하여 푸는 문제이다.

특정 노드부터 시작하라는 말이 없기에 크루스칼 알고리즘을 사용하였다.

(꼭 저 말이 있어야만 프림 알고리즘을 사용할 수 있는 것은 아니지만, 크루스칼 알고리즘의 성능이 더 좋다.)

 

보통의 크루스칼 알고리즘 문제들은 연결되는 두 노드와 간선의 비용을 입력하도록 한다.

하지만 이 문제에서는 모든 행성이 연결되어 있고, 각각의 행성마다 비용을 입력하게 되어있다.

즉, 우선순위 큐에 연결된 두 노드와 간선의 비용을 넣어주는 작업을 따로 해줘야 한다는 것이다.

이 때, 자기 자신과 연결된 간선의 비용은 0이므로 고려해주지 않았다.

 

위의 과정이 끝났다면 남은 것은 크루스칼 알고리즘의 기본이다.

부모 노드가 같은 지를 확인하고, 같지 않다면 합친다.

크루스칼 알고리즘에 대해 잘 모른다면 다음 글을 읽어보길 바란다.

https://jjunsu.tistory.com/221 

[알고리즘] 크루스칼 알고리즘(Kruscal Algorithm)

소스 코드

import java.util.*

private var n = 0
private lateinit var parent: IntArray
private lateinit var connectCost: Array<IntArray>
private var pq = PriorityQueue<Info>()

data class Info(val start: Int, val end: Int, val cost: Int): Comparable<Info> {
    override fun compareTo(other: Info): Int = cost - other.cost
}

fun main() = with(System.`in`.bufferedReader()) {
    n = readLine().toInt()
    var st: StringTokenizer

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

    connectCost = Array(n) { IntArray(n) }
    repeat(n) { i ->
        st = StringTokenizer(readLine())
        repeat(n) { j ->
            connectCost[i][j] = st.nextToken().toInt()
        }
    }

    saveCost()
    val edgeCnt = n * n - n

    var ans = 0L
    for(i in 0 until edgeCnt) {
        val cur = pq.poll()
        if(find(cur.start) != find(cur.end)) {
            union(cur.start, cur.end)
            ans += cur.cost
        }
    }

    println(ans)
}

private fun saveCost() {
    for(i in 0 until n) {
        for(j in 0 until n) {
            if(i == j) continue
            pq.add(Info(i, j, connectCost[i][j]))
        }
    }
}

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]
}