[백준] 11779 최소비용 구하기 2

 

🔒 문제

 

🧠 아이디어

그래프상 간선과 정점이 주어지고 시작점 - 목적지 - 간선비용을 입력받는 전형적인 최소 비용 경로 문제.

단 경로 과정을 모두 킵해야 하므로 다익스트라 알고리즘 상에서

특정 지점에 도착하기 직전 지점을 배열에 담아 보관하고 시작점에 도달하기 까지 목적지로부터 거꾸로 출력해내기만 하면 되겠다.

 

🔑 Kotlin Code

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.StringBuilder
import java.util.*
import kotlin.collections.ArrayList

fun dijkstra(startVertexNum: Int, distances: Array<Int>, preVertexes: Array<Int>, adjacentList: Array<ArrayList<IntArray>>, priorityQueue: PriorityQueue<IntArray>) {
    distances[startVertexNum] = 0
//    첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.
//둘째 줄에는 그러한 최소 비용을 갖는 경로에 포함되어있는 도시의 개수를 출력한다. 출발 도시와 도착 도시도 포함한다.
//셋째 줄에는 최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력한다.
    priorityQueue.add(intArrayOf(startVertexNum, distances[startVertexNum]))

    while (priorityQueue.isNotEmpty()) {
        val (minVertexNum, totalWeight) = priorityQueue.poll()
        // 구버전 정보인 경우 skip
        if (distances[minVertexNum] != totalWeight) continue

        for (adjacentVertex in adjacentList[minVertexNum]) {
            val (toVertexNum, toWeight) = adjacentVertex
            // 기존 거리가 더 짧으면 skip
            if (distances[toVertexNum] <= totalWeight + toWeight) continue
            distances[toVertexNum] = totalWeight + toWeight
            priorityQueue.add(intArrayOf(toVertexNum, distances[toVertexNum]))
            // 목적지 직전의 vertex 번호로 업데이트
            preVertexes[toVertexNum] = minVertexNum
        }
    }
}

fun main() {
    val bufferedReader = BufferedReader(InputStreamReader(System.`in`))
    val stringBuilder = StringBuilder()

    val V = bufferedReader.readLine().toInt()
    val E = bufferedReader.readLine().toInt()

    // distance (index: toVertexNum, value: distance) 배열 초기화
    val distances = Array<Int>(V + 1){ Int.MAX_VALUE }
    // index: toVertexNum, value: previous vertex num
    val preVertexes = Array<Int>(V + 1){0}

    // index: from vertex num, IntArray[0]: to vertex num, IntArray[1]: weight
    val adjacentList = Array<ArrayList<IntArray>>(V + 1){ArrayList<IntArray>()}

    repeat(E){
        val (from, to, weight) = bufferedReader.readLine().split(" ").map{it.toInt()}
        adjacentList[from].add(intArrayOf(to, weight))
    }

    val (startVertexNum, endVertexNum) = bufferedReader.readLine().split(" ").map{it.toInt()}

    // weight min heap
    val priorityQueue = PriorityQueue<IntArray>(E + 1){arr1, arr2-> arr1[1].compareTo(arr2[1])}

    dijkstra(startVertexNum, distances, preVertexes, adjacentList, priorityQueue)

    // distances, preVertexes 업데이트 완료
    stringBuilder.append("${distances[endVertexNum]}\n")

    val paths = Stack<Int>()

    var previousVertexNum = endVertexNum
    paths.push(endVertexNum)
    while(previousVertexNum != startVertexNum) {
        previousVertexNum = preVertexes[previousVertexNum]
        paths.push(previousVertexNum)
    }
    stringBuilder.append("${paths.size}\n")

    while (paths.isNotEmpty()) {
        val vertex = paths.pop()
        stringBuilder.append("$vertex ")
    }
    println(stringBuilder.toString())
}