[백준 1197번] [Kotlin] 최소 스패닝 트리

 

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

1197번: 최소 스패닝 트리

 

난이도 : 골드 4
태그 : 그래프 이론, 최소 스패닝 트리

 

 

설명

최소 스패닝 트리의 입문 문제입니다.

응용문제가 아니기에, 연습용으로 제격인 문제네요.

 

최소 스패닝 트리를 모르신다면 아래 포스팅을 참고해주세요.

https://uknowblog.tistory.com/294

[알고리즘] 최소 스패닝 트리 (MST, Minimum Spanning Tree)

 

 

 

소스코드

import java.util.PriorityQueue
import java.util.StringTokenizer

data class Node(val from: Int, val to: Int, val weight: Int) : Comparable<Node> {
    override fun compareTo(o: Node): Int {
        return this.weight - o.weight
    }
}

lateinit var parent: Array<Int>

fun main() = with(System.`in`.bufferedReader()) {
    val (v, e) = readLine().split(" ").map { it.toInt() }

    val pq = PriorityQueue<Node>()
    parent = Array(v + 1) { it }

    repeat(e) {
        val st = StringTokenizer(readLine())
        pq.offer(Node(st.nextToken().toInt(), st.nextToken().toInt(), st.nextToken().toInt()))
    }

    var total = 0

    while (pq.isNotEmpty()) {
        val target = pq.poll()
        if (union(target.from, target.to)) total += target.weight
    }

    println(total)
}

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

fun union(x: Int, y: Int): Boolean {
    val nx = find(x)
    val ny = find(y)

    return if (nx != ny) {
        parent[nx] = ny
        true
    } else false
}

 

저는 크루스칼 알고리즘을 사용해 풀이하였습니다.

먼저, 시작 노드, 도착 노드, 간선의 비용을 담을 데이터용 클래스 Node를 만들고,

간선을 기준으로 정렬하기 위해 Comparable을 상속받아 compareTo 메소드를 오버라이딩 하였습니다.

 

이후,  모든 간선의 정보를 큐에 넣어준 뒤

큐에서 Node를 하나씩 꺼내며 union - find를 통해 간선을 하나씩 이어줍니다.

union 과정에서, 두 노드가 이미 이어져 있으면 (두 노드의 부모가 같으면) false를 반환하고

두 노드가 이어져있지 않으면 두 노드를 서로 이어주고 (노드의 부모를 같게 만듬) true를 반환합니다.

 

true를 반환한 경우에만 가중치를 sum에 저장한다면,

최소 스패닝 트리의 가중치의 합을 구할 수 있습니다.

 

 

 

후기

최소 스패닝 트리를 연습하기에 꽤 좋았던 문제였습니다.

최소 스패닝 트리를 처음 접해봤을 때, 이게 뭐지... 했던게 기억납니다...

하지만 관련 문제도 많이 풀고, 반복해서 학습하니 이제 대충 어떤 원리인지 알 것 같네요.