MST: Kruskal Algorithm과 Prim Algorithm

팁.
1. 일단 유니온 파인드를 위한 3가지 함수를 만든다. (findUnion, isUnion, union)
2. Kruskal 알고리즘은 cost가 작은 것부터 union이 되지 않은 것이면 추가해나가는 방식이다.
고로, 정렬하여 가장 작은 것부터 시작하면 되지만 편리하게 PriorityQueue로 담아놓고 cost를 기준으로 최소값부터 뽑도록 하면 끝.

단, MST를 풀때 Kruskal만 맹신해선 안된다.

BOJ 2887 (행성 터널) 문제의 경우, 정점이 최대 100,000개 있다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.math.abs

class BOJ_행성터널 {
    lateinit var planet: Array<List<Long>>
    lateinit var root: IntArray
    fun main() {
        val br = BufferedReader(InputStreamReader(System.`in`))
        val bw = BufferedWriter(OutputStreamWriter(System.`out`))
        val n = br.readLine().toInt()
        planet = Array(n) { emptyList<Long>() }
        root = IntArray(n) { it }
        for (i in 0 until n) {
            planet[i] = br.readLine().split(" ").map { it.toLong() }
        }

        val pq = PriorityQueue<List<Long>>(compareBy { it.last() })
        for (i in planet.indices) {
            for (j in i + 1 until planet.size) {
                pq.offer(listOf(i.toLong(), j.toLong(), getDistance(i, j)))
            }
        }

        var answer = 0L
        while (pq.isNotEmpty()) {
            val (aLong, bLong, dist) = pq.poll()
            val a = aLong.toInt()
            val b = bLong.toInt()
            if (isUnion(a, b)) continue
            union(a, b)
            answer += dist
        }
        bw.write("$answer")
        br.close()
        bw.close()
    }

    fun getDistance(planetA: Int, planetB: Int): Long {
        val a = planet[planetA]
        val b = planet[planetB]
        return minOf(abs(a[0] - b[0]), abs(a[1] - b[1]), abs(a[2] - b[2]))
    }

    fun union(a: Int, b: Int) {
        val (min, max) = listOf(findUnion(a), findUnion(b)).sorted()
        root[max] = min
    }

    fun isUnion(a: Int, b: Int): Boolean {
        return findUnion(a) == findUnion(b)
    }

    fun findUnion(a: Int): Int {
        if (a == root[a]) return a
        root[a] = findUnion(root[a])
        return root[a]
    }
}

이렇게 풀면 다른 문제처럼 쉽게 통과가 될거라 생각했지만, 바로 메모리초과.
왜냐하면, 다른 문제들은 모두 2가지 경우였기 때문이다.
1. 정점의 숫자가 적었으므로, 필연적으로 간선의 개수 또한 적었음
2. 정점의 숫자가 많더라도, 정점이 일부만 연결되는 등 간선의 개수가 적었음

이렇듯 형편좋게 간선의 개수가 작았으므로 쉽게 통과가능했다.
하지만 이 문제는 아니다. 정점이 10만개이므로, 간선은 무려 (10만 - 1)!개.
몇십억은 충분히 넘을 것이다. 인터넷의 팩토리얼 계산기도 한도가 5천에 불과함.

Kruskal이 아닌 다른 알고리즘으로는 Prim 알고리즘. 근데 Prim으로 이걸 해도
n이 10만이므로, n^2 = 100억이다.
사실 Kruskal로도 풀 수있다. xyz를 정직하게 다 저장하는게 아닌 다른 방법으로.
https://chanhuiseok.github.io/posts/baek-34/

크루스칼과 프림의 차이는
https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html
이 분이 잘 정리해주셨다.

프림 알고리즘은 다익스트라와 작동방식이 비슷하다고 한다.
https://www.apexcel.blog/algorithm/graph/mst/mst/
크루스칼과 다르게 프림의 경우 각 정점의 정보가 필요하기 때문에 각 정점마다 인접한 정점의 정보를 가지고 있어야한다. 따라서 2차원 배열에 각 정점의 인접 정점의 정보를 담아준다.

정리하면,

• Kruskal 알고리즘의 시간 복잡도는 O(elog₂e)
• Prim의 알고리즘의 시간 복잡도는 O(n^2)
• 그래프 내에 적은 숫자의 간선만을 가지는 ‘희소 그래프(Sparse Graph)’의 경우 Kruskal 알고리즘이 적합하고
• 그래프에 간선이 많이 존재하는 ‘밀집 그래프(Dense Graph)’ 의 경우는 Prim 알고리즘이 적합하다.

Prim 알고리즘은 유니온파인드를 쓰지 않아도 되기에 편할듯하다.