[백준] 16398번 행성 연결

백준 16398번 - 행성 연결

문제

홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다.

두 행성 간에 플로우를 설치하면 제국의 함선과 무역선들은 한 행성에서 다른 행성으로 무시할 수 있을 만큼 짧은 시간만에 이동할 수 있다. 하지만, 치안을 유지하기 위해서 플로우 내에 제국군을 주둔시켜야 한다.

모든 행성 간에 플로우를 설치하고 플로우 내에 제국군을 주둔하면, 제국의 제정이 악화되기 때문에 황제 윤석이는 제국의 모든 행성을 연결하면서 플로우 관리 비용을 최소한으로 하려 한다.

N개의 행성은 정수 1,…,N으로 표시하고, 행성 i와 행성 j사이의 플로우 관리비용은 Cij이며, i = j인 경우 항상 0이다.

제국의 참모인 당신은 제국의 황제 윤석이를 도와 제국 내 모든 행성을 연결하고, 그 유지비용을 최소화하자. 이때 플로우의 설치비용은 무시하기로 한다.

접근 방법

모든 정점이 포함된 자료구조로 접근하기 위해서 Spanning Tree를 사용한다.

Spanning Tree: 모든 정점이 포함된 트리

이 중에서 간선의 합이 최소가 되는 Spanning Tree를 Minimum Spanning Tree(MST)라고 부른다.

MST Tree는 Greedy 방법 중 하나이고, MST를 만드는 방법으로 kruskal algorithm, prim algorithm을 사용해서 구현한다.

Kruskal은 간선들 중에 가중치가 낮은 간선부터 확인하고 순환구조가 생기지 않게 주의하며 간선을 선택한다. Spanning Tree의 특징인 edge가 정점 - 1 개가 되면 탐색을 멈춘다.

순환구조가 생기지 않기 위한 방법으로 union-find algorithm을 사용한다.

이 문제는 Kruskal algorithm을 사용해 MST를 구현하였다.

Prim은 다음에 기회가 된다면 사용해보려고 한다.

코드

class IO16398 {
    private val br = System.`in`.bufferedReader()
    private val bw = System.out.bufferedWriter()

    fun close() = bw.close()
    fun write(message: String) = bw.write(message)
    fun getN() = br.readLine().toInt()
    fun getFlowRow() = br.readLine().split(" ").map { it.toInt() }
}

fun main() {
    var answer: Long = 0
    var edges = 0
    val io = IO16398()

    val N = io.getN()

    data class Flow(val planet1: Int, val planet2: Int, val cost: Int)
    val connected = Array(N) { it } // 0 미연결, 1 연결

    val flows = mutableListOf<Flow>()

    repeat(N) { from ->
        val row = io.getFlowRow()
        for (to in from+1 until N) {
            flows.add(Flow(from, to, row[to]))
        }
    }

    fun checkAllConnection(): Boolean {
        return edges == N -1
    }

    fun findParent(p1: Int): Int {
        if (connected[p1] != p1) connected[p1] = findParent(connected[p1])
        return connected[p1]
    }

    fun findUnion(p1: Int, p2: Int): Boolean {
        var parent1 = findParent(p1)
        var parent2 = findParent(p2)
        return if (parent1 == parent2) {
            true
        } else {
            connected[parent1] = parent2
            false
        }
    }

    flows.sortBy { it.cost }

    run loop@ {
        flows.forEach { flow ->
            if (checkAllConnection()) {
                return@loop
            }
            val (p1, p2, cost) = flow
            val result = findUnion(p1, p2)
            if (result) {
                return@forEach
            } else {
                answer += cost
                edges++
            }
        }
    }
    io.write(answer.toString())
    io.close()
}