[백준/BOJ] 11779번: 최소비용 구하기 2

문제

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

11779번: 최소비용 구하기 2

해설

https://jjunsu.tistory.com/249에서 했던 1916번: 최소비용 구하기 문제의 상위 버전이다.

최소 비용을 구한 후, 몇 개의 도시를 거쳤는지, 어떤 도시를 방문했는지를 같이 출력해야 한다.

최소 비용을 구하는 방법은 위 문제와 같이 다익스트라 알고리즘을 사용하여 구하면 된다.

이제 어떠한 도시를 거쳤는지 경로를 알아야 한다.

어렵게 생각할 필요가 없다.

경로를 저장할 배열을 하나 선언한다.

이 배열은 다음 정점에 방문하기 직전 어떤 도시를 방문했는지 저장해줄 것이다.

배열명을 parent라 했을 때, parent[nextCity] = curCity가 되는 것이다.

다익스트라 알고리즘의 수행이 끝났다면, 위 배열을 통해 어떤 도시를 거쳤는지 알 수 있다.

문제의 예시를 보며 따라가보자.

※ 예시에서는 답이 1, 3, 5로 되있지만, 1, 4, 5 또한 최소 비용으로 갈 수 있기에 정답이다.

다익스트라 알고리즘을 다 수행하면, parent[5] = 4, parent[4] = 1, parent[1] = 초기값이라는 것을 알 수 있다.

이제 경로를 저장할 stack을 선언한다. stack이 아니어도 되지만, 마지막에 출력할 때, 순서대로 출력하기 편하게 하기 위해 stack을 사용하였다.

temp라는 변수를 선언하여 parent[end]의 값부터 시작하여 0이 될 때까지 반복하면서 temp를 stack에 저장해준다.

모두 끝났다면 출력 조건에 따라 출력을 해주면 된다.

코드

import java.util.*
import kotlin.collections.ArrayList

data class Info(val city: Int, val cost: Long): Comparable<Info> {
    override fun compareTo(other: Info): Int {
        return if(cost < other.cost) -1
        else 1
    }
}

private lateinit var route: Array<ArrayList<Pair<Int, Int>>>
private lateinit var parent: IntArray

fun main() = with(System.`in`.bufferedReader()) {
    val cityCnt = readLine().toInt()
    val busCnt = readLine().toInt()

    route = Array(cityCnt + 1) { ArrayList() }
    parent = IntArray(cityCnt + 1)

    repeat(busCnt) {
        val (from, to, cost) = readLine().split(" ").map { it.toInt() }
        route[from].add(Pair(to, cost))
    }

    val (start, end) = readLine().split(" ").map { it.toInt() }

    val cost = dijkstra(cityCnt, start, end)

    val visited = Stack<Int>()
    visited.add(end)
    var temp = parent[end]

    while(temp != 0) {
        visited.add(temp)
        temp = parent[temp]
    }

    println(cost)
    println(visited.size)
    while(visited.isNotEmpty()) print("${visited.pop()} ")
}

private fun dijkstra(n: Int, start: Int, end: Int): Long {
    val minCost = LongArray(n + 1) { Long.MAX_VALUE }
    val pq = PriorityQueue<Info>()
    pq.add(Info(start, 0))
    minCost[start] = 0

    while(pq.isNotEmpty()) {
        val cur = pq.poll()
        val curCity = cur.city
        val curCost = cur.cost

        if(curCity == end) return curCost
        if(curCost > minCost[curCity]) continue

        for(i in route[curCity].indices) {
            val nextCity = route[curCity][i].first
            val nextCost = curCost + route[curCity][i].second

            if(minCost[nextCity] > nextCost) {
                parent[nextCity] = curCity
                minCost[nextCity] = nextCost
                pq.add(Info(nextCity, nextCost))
            }
        }
    }

    return 0
}