백준 16202 MST 게임 Kotlin (크루스칼)

문제 출처 : https://www.acmicpc.net/problem/16202

16202번: MST 게임

문제

N개의 정점과 M개의 양방향간선으로 이루어진 단순 그래프 G가 있다. 단순 그래프란, self-loop 간선(한 정점에서 자기 자신을 이어주는 간선)이 없고, 임의의 두 정점 사이 최대 한 개의 간선이 있는 그래프를 말한다. 단순 그래프의 스패닝 트리(Spanning Tree)는 다음 조건을 만족하는 간선의 집합이다.

1. 스패닝 트리를 구성하는 간선의 개수는 N-1개이다.
2. 그래프의 임의의 두 정점을 골랐을 때, 스패닝 트리에 속하는 간선만 이용해서 두 정점을 연결하는 경로를 구성할 수 있어야 한다.

스패닝 트리 중에서 간선의 가중치의 합이 최소인 것을 최소 스패닝 트리(Minimum Spanning Tree, MST)라고 부른다.

이제 그래프에서 MST 게임을 하려고 한다.

• MST 게임은 그래프에서 간선을 하나씩 제거하면서 MST의 비용을 구하는 게임이다. MST의 비용이란 MST를 이루고 있는 가중치의 합을 의미한다. 각 턴의 점수는 해당 턴에서 찾은 MST의 비용이 된다. 
• 이 과정은 K턴에 걸쳐서 진행되며, 첫 턴에는 입력으로 주어진 그래프의 MST 비용을 구해야 한다.
• 각 턴이 종료된 후에는 그 턴에서 구한 MST에서 가장 가중치가 작은 간선 하나를 제거한다.
• 한 번 제거된 간선은 이후의 턴에서 사용할 수 없다.
• 어떤 턴에서 MST를 만들 수 없다면, 그 턴의 점수는 0이다. 당연히 이후 모든 턴의 점수도 0점이다. 첫 턴에 MST를 만들 수 없는 경우도 있다.

양방향 간선으로 이루어진 단순 그래프와 K가 주어졌을 때, 각 턴의 점수가 몇 점인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 그래프 정점의 개수 N, 그래프 간선의 개수 M, 턴의 수 K가 주어진다. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ min(10,000, N×(N-1)/2), 1 < K ≤ 100)

그 후 M개의 줄에 간선의 정보가 주어진다. 간선의 정보는 간선을 연결하는 두 정점의 번호 x, y로 이루어져 있다. 같은 간선이 여러 번 주어지는 경우는 없다. 간선의 가중치는 주어지는 순서대로 1, 2, ..., M이다.

정점의 번호는 1부터 N까지로 이루어져 있다.

출력

한 줄에 공백으로 구분하여 K개의 정수를 출력해야 한다. K개의 정수는 각 턴에 얻는 점수를 나타낸다. 

힌트

 

첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다.

두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있는 간선을 이용해 MST를 찾아야 한다. 하지만, (2, 4)를 없앤 후 MST가 존재하지 않기 때문에, 두 번째 턴과 그 이후 모든 턴의 점수는 0이 된다.

알고리즘 분류

• 그래프 이론
• 최소 스패닝 트리

풀이

최소 스패닝 트리 (MST) 기본 문제.

MST 알고리즘에는 크루스칼과 프림 알고리즘이 있는데 본인은 크루스칼 알고리즘으로 풀었다.

둘 다 안 푼지 오래됐지만 union-find 문제를 풀 일이 별로 없기에 크루스칼로 풀어봤다.

 

전체적인 풀이는 다음과 같다.

매 턴마다 가장 가중치가 낮은 간선 (현재 가중치는 오름차순 되어있으므로 앞 인덱스부터 빼면 된다)를 제거해 나가면서 남은 간선으로 MST를 완성한다.

MST를 만드는 로직은 다음과 같다.

1. 가중치가 낮은 간선을 선택한다.

2. 두 정점이 연결되어있지 않다면 연결한다. (unionParent)

3. 두 정점이 연결되어있는지 확인, 연결 모든 과정에는 find 개념이 사용되는데 아래 getParent(x: Int)함수가 find를 구현한 것이다.

4. 모든 간선을 연결한 후 모든 정점이 연결되어있는지 확인한다. (isConnected)

5. 다음 턴을 위해 parent 배열을 초기화한다.

 

union - find 알고리즘에 대한 개념은 생략~!

크루스칼과 프림 알고리즘에 대한 설명은 아래에서 확인할 수 있다.

2021.12.15 - [알고리즘] - [알고리즘] 크루스칼(Kruskal)과 프림(Prim)

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getStr() = br.readLine().trim()
fun getInt() = br.readLine().trim().toInt()

data class Edge(
    val s: Int,
    val e: Int,
    val w: Int
)
lateinit var parent: IntArray

fun clear(){
    for(i in parent.indices){
        parent[i] = i
    }
}

fun getParent(x: Int): Int{
    return if(parent[x] == x) x else getParent(parent[x]).also{
        parent[x] = it
    }
}

fun unionParent(x: Int, y: Int){
    val xx = getParent(x)
    val yy = getParent(y)
    if(parent[xx] < parent[yy]){
        parent[yy] = xx
    }else{
        parent[xx] = yy
    }
}

fun isConnected(x: Int, y: Int): Boolean{
    return getParent(x) == getParent(y)
}

fun isMST(): Boolean{
    val x = getParent(1)
    for(y in 1 until parent.size){
        if (x != getParent(y)) return false
    }
    return true
}

fun main() = with(System.out.bufferedWriter()){
    //input
    val (n,m,t) = getIntList()
    val edges = Array(m){
        val input = getIntList()
        Edge(input[0], input[1], it+1)
    }
    parent = IntArray(n+1){it}
    val answer = IntArray(t)
    for(turn in 0 until t){
        var turnResult = 0
        for(i in turn until edges.size){
            val (s,e,w) = edges[i]
            if(isConnected(s,e).not()){
                unionParent(s,e)
                turnResult += w
            }
        }
        if(isMST()) answer[turn] = turnResult
        clear()
    }
    write(answer.joinToString(" "))
    close()
}