[kotlin, 프로그래머스] 최소신장트리

문제와 입출력

최소 신장 트리 (Minimum Spanning Tree, MST)의 정의와 특징

정의

최소 신장 트리는 가중치가 할당된 무방향 그래프에서 모든 정점을 포함하면서 간선의 가중치 합이 최소가 되는 트리입니다.

특징

1. 트리의 간선 수: (V - 1)개의 간선을 가집니다.
2. 사이클 없음: 트리 구조이므로 사이클을 형성하지 않습니다.
3. 가중치 최소화: 모든 정점을 연결하면서 간선의 가중치 합이 최소가 되어야 합니다.

사용 예

1. 통신 네트워크 구축: 노드들을 가장 적은 비용으로 연결할 때 사용됩니다.

최소신장트리(MST) 구현 방법 - 크루스칼 알고리즘, 프림 알고리즘 사용 

크루스칼

간선을 가중치 순으로 정렬 후, 작은 것부터 선택 (사이클 방지)

간선 정렬 + 유니온 파인드 (Union-Find)

프림

정점 기준으로, 현재 트리에 연결 가능한 최소 비용 간선을 선택

우선순위 큐 (Min Heap) 이용

프림 알고리즘 풀이 

package com.chanhue.algorithm.백준.골드

import java.util.*

fun main() {
    val (v, e) = readLine()!!.split(" ").map { it.toInt() }
    val graph = Array(v + 1) { mutableListOf<Pair<Int, Int>>() }

    repeat(e) {
        val (a, b, c) = readLine()!!.split(" ").map { it.toInt() }
        graph[a].add(Pair(c, b))
        graph[b].add(Pair(c, a))
    }

    val visited = BooleanArray(v + 1)
    val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.first })

    pq.add(Pair(0, 1)) // 가중치, 정점
    var mstWeight = 0

    while (pq.isNotEmpty()) {
        val (cost, u) = pq.poll()
        if (visited[u] != true) { // 이미 방문한 노드가 아니라면
            visited[u] = true
            mstWeight += cost

            for ((edgeCost, next) in graph[u]) { // 정점을 기준으로 연결되어 있는 애들 추가 
                if (!visited[next]) {
                    pq.add(Pair(edgeCost, next))
                }
            }
        }
    }

    println(mstWeight)
}

큐 변화 요약 정리(프림 알고리즘)

 step              queue                                                                처리내용

0	(0, 1)	1번 시작
1	(1, 2), (3, 3)	2번으로 이동
2	(2, 3), (3, 3)	3번으로 이동
3	(3, 3)	3번 이미 방문 → 스킵

문제 풀이 포인트

 

• 항상 제일 비용 작은 간선을 먼저 선택
• 이미 방문한 정점은 무시
• 아직 방문하지 않은 정점은 계속 이어나감

 

크루스칼 알고리즘 풀이

fun main() {
    val (v, e) = readLine()!!.split(" ").map { it.toInt() }
    val edges = mutableListOf<Triple<Int, Int, Int>>()

    repeat(e) {
        val (a, b, c) = readLine()!!.split(" ").map { it.toInt() }
        edges.add(Triple(c, a, b))
    }

    edges.sortBy { it.first }

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

    fun find(x: Int): Int {
        if (parent[x] != x) {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }

    fun union(x: Int, y: Int): Boolean {
        val xRoot = find(x)
        val yRoot = find(y)
        if (xRoot == yRoot)
            return false
        else {
            parent[yRoot] = xRoot
            return true
        }

    }

    var mstWeight = 0

    for ((cost, a, b) in edges) {
        if (union(a, b)) {
            mstWeight += cost
        }
    }

    println(mstWeight)
}

 

 

순서	간선 (cost, a-b)	find(a), find(b)결과	사이클?	처리 후 parent	총 가중치
1	(1, 1-2)	1, 2	❌	1과 2 연결	+1
2	(2, 2-3)	1, 3	❌	1과 3 연결	+2
3	(3, 1-3)	1, 1	⭕️ (사이클)	추가 안 함	유지

 

크루스칼 알고리즘 핵심 정리

"모든 간선을 가중치 순으로 정렬하고, 사이클이 생기지 않으면 선택하는 알고리즘"

• 간선들을 가중치 기준으로 정렬
• 가벼운(작은) 간선부터 하나씩 추가
• 추가할 때 Union-Find(유니온 파인드) 자료구조로 "같은 그룹인지" 체크
• 같은 그룹이면 사이클이 생기니까 추가 하지 않음 , 다른 그룹이면 추가 함