[백준 1197] - 최소 스패닝 트리(Kotlin)[Kotlin]

문제

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

1197번: 최소 스패닝 트리

 

문제 풀이

MST를 구현하는 기본적인 문제이다.

우선 MST가 무엇인지에 대해서 알아야 한다.

MST는 Minimum Spanning Tree이다.

 

Spanning Tree의 조건은 V개의 정점이 있다면 V-1개의 간선을 이용해서 모든 정점을 연결할 수 있어야 한다.

그렇다면 MST는 모든 정점을 연결하면서 가중치의 합이 최소가 되어야 한다.

물론 그래프마다 여러 개의 MST가 존재할 수 있다.

 

MST를 구현하는 알고리즘은 Kruscal과 Prim이 있지만, 해당 문제는 Kruscal을 이용해서 해결했다.

 

크루스칼 알고리즘의 특징은 가중치를 오름차순으로 정렬해서, 간선을 선택하는 과정에서 사이클을 구성하는지 검사한다.

사이클을 이룬다는것은 어떻게 알 수 있을까?

예를 들어서 (1,2) 연결, (3,4) 연결, (2,3)이 연결되어 있다면 여기서 (1,2)를 연결한다면 사이클을 구성할 것이다.

즉 사이클을 검사하기 위해서는 정점들이 어떠한 부모 노드랑 연결되어 있는지 검사해야 한다.

같은 부모를 가지는 경우에는 사이클을 구성하기 때문에 추가해서는 안된다.

같은 부모를 가지지 않을 경우 간선 집합에 추가해 주면 된다.

이를 Union & Find라고 한다.

 

요약하자면

1. 모든 간선들을 가중치별로 오름차순 정렬하고
2. 간선을 추가하는 과정에서 사이클을 이루는지 검사해야 한다.(Find)
3. 사이클을 이루지 않는다면 합쳐준다. (Union)

전체 코드

package MST.`1197_최소스패닝트리`.LJH

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

class `1197` {

    private val br = BufferedReader(InputStreamReader(System.`in`))
    val array = PriorityQueue<node>(compareBy({ +it.value }))
    lateinit var parent: Array<Int>

    init {
        input()
        print(makeTree())
    }

    fun input() {
        val line = br.readLine().split(" ")
        val v = line[0].toInt()
        val e = line[1].toInt()
        parent = Array(v + 1) { it }
        repeat(e) {
            val input = br.readLine().split(" ")
            val start = input[0].toInt()
            val end = input[1].toInt()
            val weight = input[2].toInt()
            array.add(node(start, end, weight))
        }
    }

    fun makeTree(): Int {
        var answer = 0
        while(array.isNotEmpty()) {
            val edge = array.poll()
            if (find(edge.start) != find(edge.from)) { //부모가 다를 경우
                union(edge)
                answer += edge.value
            }
        }
        return answer
    }

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

    fun union(edge: node) {
        val startParent = parent[edge.start]
        val fromParent = parent[edge.from]
        if (startParent > fromParent) {
            parent[startParent] = parent[fromParent]
        } else parent[fromParent] = parent[startParent]
    }

    data class node(val start: Int, val from: Int, val value: Int)
}


fun main() {
    val solution = `1197`()
}package MST.`1197_최소스패닝트리`.LJH

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

class `1197` {

    private val br = BufferedReader(InputStreamReader(System.`in`))
    val array = PriorityQueue<node>(compareBy({ +it.value }))
    lateinit var parent: Array<Int>

    init {
        input()
        print(makeTree())
    }

    fun input() {
        val line = br.readLine().split(" ")
        val v = line[0].toInt()
        val e = line[1].toInt()
        parent = Array(v + 1) { it }
        repeat(e) {
            val input = br.readLine().split(" ")
            val start = input[0].toInt()
            val end = input[1].toInt()
            val weight = input[2].toInt()
            array.add(node(start, end, weight))
        }
    }

    fun makeTree(): Int {
        var answer = 0
        while(array.isNotEmpty()) {
            val edge = array.poll()
            if (find(edge.start) != find(edge.from)) { //부모가 다를 경우
                union(edge)
                answer += edge.value
            }
        }
        return answer
    }

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

    fun union(edge: node) {
        val startParent = parent[edge.start]
        val fromParent = parent[edge.from]
        if (startParent > fromParent) {
            parent[startParent] = parent[fromParent]
        } else parent[fromParent] = parent[startParent]
    }

    data class node(val start: Int, val from: Int, val value: Int)
}


fun main() {
    val solution = `1197`()
}