[6개월 안에 백준 플래티넘 달성하기] 17. 도시 분할 계획 1197

 

도시 분할 계획

 

문제

 

풀이

 

문제의 조건은 다음과 같습니다.

• 양방향이다.
• 마을을 두 개의 분리된 마을로 분할한다.
• 마을과 마을 사이에는 길이 존재하지 않는다.
• 마을 내부의 임의의 두 집 사이에는 경로가 항상 존재한다.
• 마을 내부에는 최소 하나 이상의 집이 있다.
• 위 조건을 만족하면서 유지비의 합이 최소여야 한다.

조건이 다소 많아 처음에는 흠칫하였지만 임의의 두 집 사이에는 경로가 항상 존재하며 최소 유지비를 만들어야 된다는 것에서 쉽게 최소 신장 트리 알고리즘을 생각할 수 있었습니다.

 

풀이 방법은 다음과 같습니다.

1. 전체 집을 대상으로 최소 신장 트리를 구합니다. (= 경로 최소화 작업)
2. 간선들 중에 가장 큰 유지비를 가진 가중치를 하나 제거해 줍니다.(= 마을 분리 작업)

위의 두 단계만으로 문제를 해결할 수 있습니다.

 

import java.io.StreamTokenizer
import java.util.PriorityQueue

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }

    data class Node(val num: Int, var dist: Int) : Comparable<Node> {
        override fun compareTo(other: Node): Int {
            return if (dist <= other.dist) -1
            else 1
        }
    }

    val N = input() // 집의 개수
    val M = input() // 길의 개수

    val arr = Array(N+1) { arrayListOf<Node>() }

    repeat(M) {
        val a = input()
        val b = input()
        val c = input()
        arr[a].add(Node(b, c))
        arr[b].add(Node(a, c))
    }

    var result = 0     // 유지비
    var maxValue = 0   // 마을 사이 최대 유지비

    val pq = PriorityQueue<Node>()
    val visited = BooleanArray(N+1)
    pq.add(Node(1, 0))

    // 최소 신장 트리
    while (pq.isNotEmpty()) {
        val cur = pq.poll()

        if (visited[cur.num]) continue
        visited[cur.num] = true

        if (maxValue < cur.dist) maxValue = cur.dist  // 최대 간선 갱신
        result += cur.dist

        for (next in arr[cur.num]) {
            if (!visited[next.num]) {
                pq.add(next)
            }
        }
    }

    // 최대 간선 빼줌
    print(result - maxValue)
}