[백준/BOJ] 14950번: 정복자

문제

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

14950번: 정복자

해설

모든 도시를 정복하는데 드는 최소 비용을 구하는 문제이다.

이 문장을 보고 MST 알고리즘을 떠올려야 한다.

MST를 떠올렸다면, 이를 크루스칼 알고리즘과 프림 알고리즘 중 어떤 알고리즘으로 해결할지 정해야 한다.

이 문제는 1번 도시부터 시작해서 이와 연결된 도시를 정복해나가야 한다.

따라서 프림 알고리즘이 더 적절하다 생각했다.

 

문제를 보면 "한 번 도시가 정복되면, 모든 도시는 경계를 하게 되기 때문에 모든 도로의 비용이 t만큼 증가하게 된다."라는 문장이 있다. 1번 도시의 군주가 모든 도시를 정복하고자 하는 것이므로, 1번 노드는 이미 정복되 있다하자.

그렇다면 1번 도시와, 이와 연결된 다른 도시 총 2개의 도시가 정복되고 나서부터 도로의 비용을 증가시켜주면 된다.

소스 코드

import java.util.*
import kotlin.collections.ArrayList

private lateinit var visited: BooleanArray
private lateinit var edge: Array<ArrayList<Pair<Int, Int>>>

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

fun main() = with(System.`in`.bufferedReader()) {
    val (nodeCnt, edgeCnt, increaseCost) = readLine().split(" ").map { it.toInt() }
    visited = BooleanArray(nodeCnt + 1)
    edge = Array(nodeCnt + 1) { ArrayList() }

    repeat(edgeCnt) {
        val (start, end, cost) = readLine().split(" ").map { it.toInt() }
        edge[start].add(Pair(end, cost))
        edge[end].add(Pair(start, cost))
    }

    println(prim(increaseCost))
}

private fun prim(increaseCost: Int): Long {
    var ans = 0L
    var conquer = 0
    var cnt = 0
    val pq = PriorityQueue<Move>()
    pq.add(Move(1, 0))

    while(pq.isNotEmpty()) {
        val cur = pq.poll()
        if(visited[cur.node]) continue

        conquer++
        visited[cur.node] = true

        if(conquer > 2) cnt++
        ans += cur.cost + cnt * increaseCost

        for(i in edge[cur.node].indices) {
            if(!visited[edge[cur.node][i].first]) pq.add(Move(edge[cur.node][i].first, edge[cur.node][i].second))
        }
    }

    return ans
}