[백준] 1922번: 네트워크 연결 - Kotlin[코틀린]

문제

 

1922번: 네트워크 연결

 

---

풀이

 

 이 문제는 최소 신장 트리(Minimum Spanning Tree, MST)를 구하는 것으로 크루스칼 알고리즘을 사용한다. 신장 트리란 주어진 그래프에서 일부 간선을 선택하여 모든 노드를 연결하되 싸이클이 없는 트리이다. 여러 신장 트리들 중에서 간선의 가중치의 합이 최소인 것이 최소 신장 트리이다. 최소 신장 트리를 구하는 방법인 크루스칼 알고리즘은 최소 비용으로 모든 노드를 연결하기 위해 사용한다.

 

 먼저 입력받은 그래프를 간선의 가중치를 기준으로 오름차순 정렬한다. 그 후, 가중치가 가장 낮은 간선부터 선택하여 유니온 파인드(Union-Find)를 사용해 각 정점의 연결 상태를 기록한다. 유니온 파인드를 사용하는 이유는 이미 연결된 정점들 사이의 새로운 간선을 선택하여 싸이클이 형성되는 것을 방지하는 것이다. 간선의 가중치가 낮은 순서대로 반복하여 선택하면, 최종적으로 최소 신장 트리가 완성된다.

 

---

코드

 

import java.util.*

data class Edge(val start: Int, val end: Int, val value: Int) : Comparable<Edge> { // 간선
    override fun compareTo(other: Edge): Int {
        return value - other.value
    }
}

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val num = br.readLine().toInt()
    val line = br.readLine().toInt()

    val graph = ArrayList<Edge>()
    repeat(line) {
        val (start, end, value) = br.readLine().split(' ').map { it.toInt() }
        graph.add(Edge(start, end, value))
    }

    val parent = IntArray(num + 1) { it }

    fun find(a: Int): Int {
        return if(a == parent[a]) a
        else {
            parent[a] = find(parent[a])
            parent[a]
        }
    }
    fun union(a: Int, b: Int) {
        val x = find(a)
        val y = find(b)
        if(x < y) {
            parent[y] = x
        } else {
            parent[x] = y
        }
    }

    graph.sort()

    var cost = 0
    for(edge in graph) {
        if(find(edge.start)!=find(edge.end)) { // 연결되어있지 않은 정점의 간선
            cost += edge.value
            union(edge.start, edge.end)
        }
    }

    bw.write("$cost")
    bw.flush()
    bw.close()
    br.close()
}