[백준] 1197번: 최소 스패닝 트리 - Kotlin[코틀린]

문제

 

1197번: 최소 스패닝 트리

 

---

풀이

 

 최소 스패닝 트리를 구하는 문제로 프림과 크루스칼 알고리즘을 이용해 풀이할 수 있다. 이번 문제에서는 프림 알고리즘을 사용하였다. 프림 알고리즘의 주요 단계는 다음과 같다.

 

 1. 노드 선택: 임의의 노드를 선택하여 시작한다.

 2. 우선 순위 큐 생성: 선택한 노드와 연결된 모든 간선을 우선 순위 큐에 추가한다. 이때, 간선의 가중치를 기준으로 오름 차순 정렬된다.

 3. 최소 간선 선택: 우선 순위 큐에서 가중치가 가장 작은 간선을 선택한다.

 4. 노드 추가 및 간선 연결: 선택한 간선으로 연결된 새로운 노드를 최소 스패닝 트리에 추가하고, 해당 노드와 연결된 모든 간선들을 우선 순위 큐에 추가한다.

 5. 반복: 위의 과정을 반복하여 최소 스패닝 트리를 완성한다.

 

 알고리즘의 핵심은 우선 순위 큐를 이용하여 간선의 가중치를 기준으로 정렬하고, 최소 가중치의 간선을 선택하여 트리를 확장하는 것이다. 이를 통해 최종적으로 모든 노드를 연결하는 최소 비용의 트리를 얻을 수 있다.

 

---

코드

 

import java.util.*

// 그래프의 간선 정보를 담을 클래스
class Node(val index: Int, val value: Int): Comparable<Node> {
    override fun compareTo(other: Node): Int = value - other.value
}

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    // 정점 개수와 간선 개수 입력
    var st = StringTokenizer(br.readLine())
    val vertex = st.nextToken().toInt()
    val edge = st.nextToken().toInt()

    // 그래프 생성 (인접 리스트 표현을 위한 우선순위 큐 배열)
    val graph = ArrayList<PriorityQueue<Node>>(vertex+1)
    val visited = BooleanArray(vertex+1)

    repeat(vertex + 1) { graph.add(PriorityQueue()) }

    // 간선 정보 입력 및 그래프 구성
    repeat(edge) {
        st = StringTokenizer(br.readLine())
        val start = st.nextToken().toInt()
        val end = st.nextToken().toInt()
        val value = st.nextToken().toInt()

        // 무방향 그래프이므로 양방향으로 간선 정보 추가
        graph[start].add(Node(end, value))
        graph[end].add(Node(start, value))
    }

    fun prim() : Long {
        val queue = PriorityQueue<Node>()
        var sum = 0L
        var cnt = 0

        // 임의의 시작 노드를 큐에 추가
        queue.add(Node(1, 0))

        while(queue.isNotEmpty()) {
            val tmp = queue.poll()

            // 이미 방문한 노드라면 스킵
            if(visited[tmp.index]) continue

            // 현재 노드 방문 처리 및 가중치 합산
            visited[tmp.index] = true
            sum += tmp.value

            // 트리에 연결된 미방문 노드들을 큐에 추가
            for(next in graph[tmp.index]) {
                if(!visited[next.index]) {
                    queue.add(next)
                }
            }

            // 트리의 노드 개수 증가
            if(++cnt == vertex) return sum
        }

        return sum
    }

    // 결과 출력
    bw.write("${prim()}")
    bw.flush()
    bw.close()
    br.close()
}