[6개월 안에 백준 플래티넘 달성하기] 12. 최소비용 구하기 11779

최소비용 구하기 2

 

문제

 

다익스트라를 조금만 응용하면 간단히 풀 수 있습니다.

 

풀이

도시 A에서 도시 B까지 최단 거리만 보면 다익스트라로 풀 수 있을 거 같습니다. 하지만 다익스트라만으로는 최소비용을 구할 수 있지만 경로에 포함된 도시의 개수와 경로를 방문하는 도시 순서를 얻지 못합니다. 

따라서 어느 정도 응용을 해주면 쉽게 풀 수 있습니다.

 

제가 생각한 방법은 각 도시별 최소 비용을 가지는 minDist 배열에 최단 거리 정보뿐만 아니라 이전 도시의 정보를 추가하는 것입니다. 해당 방법으로 다익스트라 알고리즘을 진행한 뒤에  minDist를 역추적하면 도시의 개수와 도시 순서를 알 수 있습니다.

 

구현 방법은 더 간단합니다. 기존 다익스트라에서 최소 비용이 갱신될 경우에 minDist에 갱신된 최소 비용을 넣어주었는데 거기에 추가적으로 도시 정보도 넣어주면 됩니다.

 

추가적으로 주의해야 될 점이 있습니다. 

1. 버스 비용은 0을 허용합니다. 따라서 초기값을 0으로 설정하면 안 됩니다.
2. 동일 노선에 다른 비용의 경로가 존재할 수 있습니다. 따라서 여러 노선 중 최소비용의 노선을 선택해야 됩니다.

 

import java.io.StreamTokenizer
import java.util.LinkedList
import java.util.PriorityQueue

fun main()= StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }
    val N = input() // 노드 개수
    val M = input() // 간선 개수

    val arr = Array(N+1) { IntArray(N+1) { Int.MAX_VALUE} }  // 버스 비용은 0을 허용, 따라서 초기값은 무한으로 설정
    repeat(M) {
        val a = input()
        val b = input()
        val c = input()
        arr[a][b] = Math.min(arr[a][b], c)  // 동일한 노선에 여러 비용이 입력될 수 있다.
    }
    for (i in 1..N) arr[i][i] = 0  // 자기 자신 도시 경로는 항상 0

    val start = input()  // 시작 지점
    val end = input()    // 도착 지점

    data class Node(val num: Int, var dist: Int)
    data class MinDist(var from: Int, var dist: Int) // 어떤 노드로부터 도달했지는, 최소거리

    val minDist = Array(N+1) { i -> MinDist(i, Int.MAX_VALUE)}
    val queue = PriorityQueue<Node>(compareBy{it.dist})

    minDist[start] = MinDist(start, 0)
    queue.add(Node(start, 0))

    while (queue.isNotEmpty()) {
        val cur = queue.poll()
        val num = cur.num

        for (next in arr[num].indices) {
            if (arr[num][next] != Int.MAX_VALUE && minDist[next].dist > arr[num][next] + minDist[num].dist) {
                minDist[next].dist = arr[num][next] + minDist[num].dist
                minDist[next].from = num  // 기존 다익스트라에서 이 부분만 추가해주면 됨
                queue.add(Node(next, minDist[next].dist))
            }
        }
    }


    // 방문 순서,  방문개수 구하기
    var count = 1
    val pathArr = LinkedList<Int>()
    var path = end
    pathArr.add(end)

    // 도착 지점에서부터 시작지점까지 경로를 구한다.
    while (path != start) {
        path = minDist[path].from
        pathArr.addFirst(path)
        count++
    }

    println(minDist[end].dist)
    println(count)
    print(pathArr.joinToString(" "))
}