[백준 27498] - 연애 혁명(Kotlin)[골드3]

문제

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

27498번: 연애 혁명

문제 풀이

저번 포스팅인 1197 최소 스패닝 트리를 풀면 아주 수월하게 풀 수 있습니다.

우선 문제가 굉장히 복잡해 보이지만, 핵심은 포기하도록 만드는 애정도의 합을 최소화하는것이 우리의 목표입니다.

우선 사랑관계는 여기서 정점들끼리의 간선으로 연결되어야한다는 뜻입니다.

문제에서 사랑관계가 이미 이루어진 관계는 반드시 포함되어야 한다고 정의했으므로,

사랑관계가 이루어진 관계는 반드시 간선에 포함시켜줘야합니다.

그러면 나머지 간선들중에서 우리는 애정도가 높은 순서대로 간선을 연결줘야합니다.

그래야 포기하게 되는 사랑관계(간선)의 애정도가 최소가 될 것입니다.

즉 요약하면

1. 사랑관계가 이루어진 간선은 반드시 포함
2. 애정도의 합이 최소가 되기 위해서는 애정도가 높은 관계부터 선택해야한다.
3. 최소 애정도의 값은 1번 단계에서 제외된 사랑관계가 이루어진 간선들의 애정도 합 - 사랑관계를 이루지 못한 간선들의 애정도 합

따라서 우선순위큐의 정렬 조건은 애정도가 높은 순서대로 정렬하면 될 것이고,

입력과정에서 사랑관계가 정의되었다면 Union 해주고, 정의되지 않은 간선들중에서 사이클이 있는지 판단하고 Union 하면 됩니다.

전체 코드

package MST.`27498_연애혁명`.LJH

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.PriorityQueue
import java.util.StringTokenizer

class `27498` {
    private val br = BufferedReader(InputStreamReader(System.`in`))
    private val pq = PriorityQueue<Node>(compareBy({-it.weight})) //성공한 놈들을 우선적으로
    private lateinit var parent: Array<Int>
    private var answer =0
    private var include =0
    init {
        input()
        makeMst()
        print(answer-include)
    }

    private fun input() {
        val line = br.readLine().split(" ")
        val v = line[0].toInt()
        val e = line[1].toInt()
        parent = Array(v+1){it}
        repeat(e) {
            val input = StringTokenizer(br.readLine())
            val from = input.nextToken().toInt()
            val to =  input.nextToken().toInt()
            val weight = input.nextToken().toInt()
            val success = input.nextToken().toInt()
            if(success==1){
                union(from,to)
            }
            else {
                answer+=weight
                pq.add(Node(from,to,weight,success))
            }
        }
    }
    fun makeMst(){
        while(pq.isNotEmpty()){
            val edge = pq.poll()
            if(find(edge.from)!=find(edge.to)){
                union(edge.from, edge.to)
                include+=edge.weight
            }
        }
    }
    private fun find(id : Int) : Int{
        if(parent[id]==id)
            return id
        parent[id] = find(parent[id])
        return parent[id]
    }
    private fun union(from : Int,to : Int){
        val fromParent = find(from)
        val toParent = find(to)
        if(fromParent>toParent)  parent[fromParent] = parent[toParent]
        else parent[toParent] = parent[fromParent]
    }
    data class Node(val from: Int, val to: Int, val weight: Int, val success: Int)
}

fun main() {
    val solution = `27498`()

}