백준 [11779] kotlin

[문제]

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

11779번: 최소비용 구하기 2

[풀이]

기존의 다익스트라 문제의 최소 비용을 저장해두는 배열에, 추가적으로 경로를 저장하는 배열을  사용한다.

 

최소 비용을 저장해두는 배열을 arr이라고 했을 때, 아래의 경우는 arr을 새롭게 갱신하는 경우이다.

이때 arr을 갱신하면서 경로추적을 위한 배열 route의 idx를 갱신해준다.

if(nextWei < arr[nextIdx])
{
    arr[nextIdx] = nextWei
    route[nextIdx] = curIdx
    pq.add(Edge(nextIdx,nextWei))
}

이렇게 만들어진 route 배열을 다음과 같이 역추적을 한다.

route 배열을 선언할 때 값을 0으로 초기화를 해주면,

start 배열의 이전 값은 0이므로 start까지 가면 while이 종료가 된다.

결과 출력은 역순으로 나오므로, reversed() 를 이용하면 경로가 나온다.

val routeList = arrayListOf<Int>()
var now = tmp[1]
while(now != 0)
{
    routeList.add(now)
    now = route[now]
}

[코드]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.PriorityQueue

lateinit var bus : Array<ArrayList<Edge>>
lateinit var arr : IntArray
lateinit var route : IntArray
data class Edge(val node : Int, val weight : Int) : Comparable<Edge>{
    override fun compareTo(other: Edge): Int {
        return weight - other.weight
    }
}
fun main()
{
    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))

    var N = br.readLine().toInt()
    var M = br.readLine().toInt()

    bus = Array(N+1){ arrayListOf() }
    arr = IntArray(N+1){Int.MAX_VALUE}
    route = IntArray(N+1){0}

    repeat(M)
    {
        val tmp = br.readLine().split(" ").map { it.toInt()}
        bus[tmp[0]].add(Edge(tmp[1],tmp[2]))
    }
    val tmp = br.readLine().split(" ").map { it.toInt() }
    dijkstra(tmp[0])
    bw.write(arr[tmp[1]].toString() + "\n")
    val routeList = arrayListOf<Int>()
    var now = tmp[1]
    while(now != 0)
    {
        routeList.add(now)
        now = route[now]
    }
    bw.write(routeList.size.toString() + "\n")
    bw.write(routeList.reversed().joinToString(" ") + "\n")
    bw.flush()
    bw.close()
}
fun dijkstra(start : Int)
{
    arr[start] = 0
    var pq = PriorityQueue<Edge>()
    pq.add(Edge(start,0))
    while (pq.isNotEmpty())
    {
        val curIdx = pq.peek().node
        val curWei = pq.peek().weight
        pq.poll()
        if(arr[curIdx] < curWei) continue
        for(i in bus[curIdx].indices)
        {
            val nextIdx = bus[curIdx][i].node
            val nextWei = curWei + bus[curIdx][i].weight
            if(nextWei < arr[nextIdx])
            {
                arr[nextIdx] = nextWei
                route[nextIdx] = curIdx
                pq.add(Edge(nextIdx,nextWei))
            }
        }
    }
}