[6개월 안에 백준 플래티넘 달성하기] 16. 최소 스패닝 트리 1197

최소 스패닝 트리

 

문제

 

풀이

최소 스패닝(신장) 트리 문제입니다.

모든 노드를 지나면서 사이클이 존재하지 않는 트리 중 간선의 합이 가장 낮은 트리를 찾으면 됩니다.

 

백준 class 4 문제를 모두 해결하신 분이라면 다익스트라 알고리즘을 살짝 응용하면 충분히 푸실 수 있을 겁니다.

저 또한 이처럼 해당 문제를 풀었고 이후 해당 풀이가 최소 신장트리를 구하는 프림 알고리즘이라는 것을 알게 되었습니다.

 

이 밖에도 크루스칼 알고리즘도 존재하는데 이 둘을 간략하게 설명드리겠습니다.

 

프림 알고리즘

최소 신장트리를 구하는 알고리즘입니다.

음의 간선이 존재하고 사이클이 존재할 때도 사용할 수 있습니다.

 

프림 알고리즘은 단순하게 노드를 하나씩 돌면서 최소 간선을 추가해 주는 방식입니다. 

따라서 주로 문제에 주어진 간선이 많을 경우 사용됩니다.

 

동작 방식은 다음과 같습니다.

1. 시작 노드를 우선순위 큐(가중치가 적은)에 담아줍니다.
2. 큐에서 노드를 빼준 뒤 방문처리를 체크하고 결과값에 가중치값을 더해줍니다.
3. 해당 노드와 연결되어 있는 주변 노드들 중 방문하지 않은 노드를 큐에 추가해 줍니다.
4. 큐가 빌 때 동안 2번과 3번을 반복해 줍니다.

 

코드로 보면 더 간단합니다.

import java.io.StreamTokenizer
import java.util.PriorityQueue

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }
    
    data class Node(val num: Int, var dist: Int) : Comparable<Node> {
        override fun compareTo(other: Node): Int {
            return if (dist <= other.dist) -1
            else 1
        }
    }

    val V = input() // 정점
    val E = input() // 간선

    val arr = Array(V+1) { arrayListOf<Node>() }

    repeat(E) {
        val a = input()
        val b = input()
        val c = input()
        arr[a].add(Node(b, c))
        arr[b].add(Node(a, c))
    }

    var result = 0
    val visited = BooleanArray(V+1)
    val pq = PriorityQueue<Node>()
    pq.add(Node(1, 0))   // 초기값은 노드1번과 가중치 0으로 설정
    
    while (pq.isNotEmpty()) {
        val cur = pq.poll()

        if (visited[cur.num]) continue
        visited[cur.num] = true
        result += cur.dist
        
        for (next in arr[cur.num]) {
            if (!visited[next.num]) {
                pq.add(next)
            }
        }
    }
    
    print(result)
}

 

 

크루스칼 알고리즘

프림 알고리즘과 같이 최소 신장트리를 구하는 데 사용되는 알고리즘입니다.

 

크루스칼 알고리즘 자체도 단순합니다.

모든 간선을 정렬한 뒤에 최소 간선을 하나씩 빼주면서 결과값에 더해주면 됩니다.

따라서 주로 문제에 주어진 간선이 적을 경우 사용됩니다.

 

다만 여기서 간선을 더해주기 전에 사이클이 생기는지 체크해 줘야 되는데 여기서는 Union-find 알고리즘이 사용됩니다.

사이클 발생되면 안됨

 

참고로 간선을 잇는 노드 1과 노드 2의 부모가 동일한 경우에 사이클이 생기기 때문에 Union-find 알고리즘을 사용합니다.

 

import java.io.StreamTokenizer
import java.util.PriorityQueue

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }
    data class Node(val num1: Int, val num2: Int, val dist: Int) : Comparable<Node> {
        override fun compareTo(other: Node): Int {
            return if (dist <= other.dist) -1
            else 1
        }
    }

    val V = input() // 정점
    val E = input() // 간선

    val edges = PriorityQueue<Node>()

    repeat(E) {
        edges.offer(Node(input(), input(), input()))
    }

    var result = 0
    val parents = IntArray(V+1) {it}

    fun find(num: Int): Int {
        if (num != parents[num])
            return find(parents[num])
        return num
    }

    fun unionFind(num1: Int, num2: Int): Boolean {
        val p1 = find(num1)
        val p2 = find(num2)
        if (p1 == p2) return false

        if (p1 > p2) {
            parents[p1] = p2
        } else {
            parents[p2] = p1
        }
        return true

    }

    while (edges.isNotEmpty()) {
        val edge = edges.poll()
        if (unionFind(edge.num1, edge.num2)) {
            result += edge.dist
        }
    }
    print(result)
}