백준 16398 행성 연결 Kotlin (mst)

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

16398번: 행성 연결

문제

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

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

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

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

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

입력

입력으로 첫 줄에 행성의 수 N (1 ≤ N ≤ 1000)이 주어진다.

두 번째 줄부터 N+1줄까지 각 행성간의 플로우 관리 비용이 N x N 행렬 (Cij),  (1 ≤ i, j ≤ N, 1 ≤ Cij ≤ 100,000,000, Cij = Cji) 로 주어진다.

출력

모든 행성을 연결했을 때, 최소 플로우의 관리비용을 출력한다.

알고리즘 분류

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

풀이

모든 노드를 연결하면서, 연결하는 데에 쓰이는 가중치를 최소로 해야 하기 때문에 최소 신장 트리(MST)를 구하는 문제이다.

MST를 구하는 알고리즘엔 프림과 크루스칼 알고리즘이 있다.

프림은 그냥 기본 프림 알고리즘을 사용하면 돼서 딱히 설명할 거리가 없다.

크루스칼은, 전체 노드가 연결되어야 하기 때문에, 여러 개의 그룹이 나올 수가 없다.

따라서 기존 크루스칼 알고리즘을 조금 변형하여,

parent 배열에 본인 노드를 저장하는 게 아니라, -1을 저장해놓고,

getParent로 현재 노드가 -1이 아닐 때, -1을 가진 루트 노드를 가져오고,

unionParent로 두 노드 x, y의 루트 노드 값이 다를 땐 y 루트 노드의 값을 x 루트 노드로 바꿈으로써

이들이 연결되었다는 것을 표현할 수 있다.

 

 

코드(프림)

import java.util.*
fun prim( n : Int, edge : Array<ArrayList<Pair<Int,Long>>>, visited: BooleanArray) : Long{

    var answer= 0L
    val pq = PriorityQueue<Pair<Int,Long>>(kotlin.Comparator {a, b ->
        when{
            a.second < b.second -> -1
            a.second == b.second -> 0
            else -> 1
        }
    })
    pq.add(Pair(0,0L))
    while(pq.isNotEmpty()){
        val cur = pq.poll()
        if(visited[cur.first]) continue
        visited[cur.first]=true
        answer+=cur.second

        for(next in edge[cur.first]){
            if(visited[next.first]) continue
            pq.add(Pair(next.first,next.second))
        }

    }
    return answer
}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val n = br.readLine().toInt()
    val edge = Array(n){ArrayList<Pair<Int,Long>>()}
    for(i in 0 until n-1){
        val line = br.readLine().split(' ').map{it.toLong()}
        for(j in i+1 until n){
            edge[i].add(Pair(j,line[j]))
            edge[j].add(Pair(i,line[j]))
        }
    }
    write("${prim(n,edge,BooleanArray(n))}")
    close()
}

코드(크루스칼)

data class Edge(var from : Int, var to : Int, var dis : Long)

val parent = IntArray(1000){-1}

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

fun unionParent(x : Int, y : Int) : Boolean{
    val xx = getParent(x)
    val yy = getParent(y)
    if(xx!=yy){
        parent[yy]=xx
        return true
    }
    return false

}


fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val n = br.readLine().toInt()
    val edge = Array((n*(n-1))/2){Edge(0,0,0)}
    var idx=0
    for(i in 0 until n-1){
        val line = br.readLine().split(' ').map{it.toLong()}
        for(j in i+1 until n){
            edge[idx++]=Edge(i,j,line[j])
        }
    }
   edge.sortBy { it.dis }
    var answer = 0L
    for(ele in edge){
        if(unionParent(ele.from,ele.to))
        answer += ele.dis
    }

    write("$answer")
    close()
}