[BaekJoon] 1922번 네트워크 연결 (Kotlin) 문제 풀이 [Gold 4]

문제

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

1922번: 네트워크 연결

 

어떻게 풀 것인가?

최소 스패닝 트리(MST) 와 그로 인한 크루스칼 알고리즘을 이용하여 문제를 해결하였다. 

아래 코드를 참고해보면 알겠지만 언뜻보면 유니온-파인드 알고리즘 처럼 보일 수 있겠으나 편의를 위해서 함수명을 그렇게 작성을 하였다.

사실 이 문제의 경우 "최소 스패닝 트리와 크루스칼 알고리즘을 알고있어?" 라는 것을 물어보는 것 같았다.

 

특수한 스킬이나 응용이 필요한 것은 없었다.

 

물론 최소 스패닝 트리와 크루스칼 알고리즘은 어렵다...

 

풀면서 놓쳤던점

X

 

이 문제를 통해 얻어갈 것

최소 스패닝 트리와 크루스칼 알고리즘 기본적인 이해

 

내 코드 

import java.util.*

// 백준알고리즘 1922번 네트워크 연결
// 최소 스패닝 트리, 크루스칼 알고리즘
data class Computer(val start: Int, val end: Int, val cost: Int) : Comparable<Computer> {
    override fun compareTo(other: Computer): Int {
        return this.cost - other.cost
    }
}

private lateinit var parent: IntArray

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val m = readLine().toInt()
    val que = PriorityQueue<Computer>()
    parent = IntArray(n + 1) { 0 }

    for (i in 1 until parent.size) {
        parent[i] = i
    }


    repeat(m) {
        val (start, end, cost) = readLine().split(" ").map { it.toInt() }
        que.offer(Computer(start, end, cost))
    }
    var result = 0
    while (que.isNotEmpty()) {
        val computer = que.poll()
        if (find(computer.start) != find(computer.end)) {
            union(computer.start, computer.end)
            result += computer.cost
        }
    }
    println(result)
}

fun union(v1: Int, v2: Int) {
    val p1 = find(v1)
    val p2 = find(v2)
    if (p1 < p2) {
        parent[p2] = p1
    } else {
        parent[p1] = p2
    }
}

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

 

참고

X