백준 10217 KCM Travel Kotlin (다익스트라)

문제 출처: https://www.acmicpc.net/problem/10217

10217번: KCM Travel

문제

각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세에 힘입어 구글 역시 대기업답게 비용 감축에 열을 내고 있었던 것이다.

초대장 내용에 의하면 구글은 찬민에게 최대 M원까지의 비용만을 여행비로써 부담해주겠다고 한다. 인천에서 LA행 직항 한 번 끊어주는게 그렇게 힘드냐고 따지고도 싶었지만, 다가올 결승 대회를 생각하면 대회 외적인 곳에 마음을 쓰고 싶지 않은 것 또한 사실이었다. 그래서 찬민은 인천에서 LA까지 M원 이하로 사용하면서 도착할 수 있는 가장 빠른 길을 차선책으로 택하기로 하였다.

각 공항들간 티켓가격과 이동시간이 주어질 때, 찬민이 인천에서 LA로 갈 수 있는 가장 빠른 길을 찾아 찬민의 대회 참가를 도와주자.

입력

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 공항의 수 N (2 ≤ N ≤ 100), 총 지원비용 M (0 ≤ M ≤ 10,000), 티켓정보의 수 K (0 ≤ K ≤ 10,000)가 공백으로 구분되어 주어진다. 이어서 K개의 줄에 걸쳐 각 티켓의 출발공항 u, 도착공항 v (1 ≤ u, v ≤ N, u ≠ v), 비용 c (1 ≤ c ≤ M, 정수), 그리고 소요시간 d (1 ≤ d ≤ 1,000) 가 공백으로 구분되어 주어진다. 인천은 언제나 1번 도시이고, LA는 언제나 N번 도시이다

출력

각 테스트 케이스당 한 줄에 찬민이 LA에 도착하는 데 걸리는 가장 짧은 소요시간을 출력한다.

만약, LA에 도착할 수 없는 경우 "Poor KCM"을 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍
• 그래프 이론
• 다익스트라

풀이

골드 1 치곤 어렵지 않은 다익스트라 문제이다.

일반적인 다익스트라로 풀면 최단 거리를 찾을 순 있으나, 그 최단 거리가 지원 비용인 M을 넘을 수도 있다.

즉 다익스트라로 최단 거리를 찾되, 지원 비용인 M이하로 금액을 사용하면서 N에 도착해야 한다.

따라서 다익스트라 알고리즘에 비용을 M이하로만 이동할 수 있게끔 

 

if(nextCost>m) continue로 m보다 커지는 경로를 차단한다.

 

기존 다익스트라는 m이라는 비용의 제한이 없기 때문에 어떠한 노드 X에 도착했을 때 최단 거리가 아니라면 탐색을 하지 않는다. 

a라는 값을 m이라는 비용 제한 없는 기존 다익스트라의 최단 경로라고 한다면, 우리가 원하는 m이라는 제한을 걸어둔 최단 거리는 a보다 클 수도 있다. 따라서 a의 경로에 해당하지 않더라도 탐색을 이어나가야 하는 것이다. 이렇게 되면 탐색이 계속 뻗어나가면서 메모리 초과가 뜰 텐데, 이때 dp를 사용할 수 있다.

dp[현재 사용한 금액][정점]

이 dp의 의미는 현재 얼마를 써서 X라는 정점에 도착을 했다는 의미이고,  간선을 걸러주는 것은

if(dp[cost][cur] < cur.dis) continue로 걸러주면 된다.

 

이후 정답은 dp[1~m][n] 중에서 가장 작은 값을 출력하면 된다.

 

코드

import java.util.*

val br = System.`in`.bufferedReader()

fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

data class Node(
    val cur: Int,
    val cost: Int,
    val dis: Int
)

var T = 0
lateinit var edge: Array<ArrayList<Node>>
lateinit var dp: Array<IntArray>
//n 2  100 공항 수
//m 0 10000 총 지원 비용
//k 0  10000 티켓 정보
//1출발 n도착

fun dijkstra(n: Int, m: Int){

    val pq = PriorityQueue<Node>(Comparator { a, b ->
        when{
            a.dis < b.dis -> -1
            a.dis == b.dis -> 0
            else -> 1
        }
    })

    pq.add(Node(1,0,0))

    while(pq.isNotEmpty()){
        val cur = pq.poll()
        if(dp[cur.cost][cur.cur] < cur.dis) continue

        for(ne in edge[cur.cur]){
            val nextDis = cur.dis+ne.dis
            val next = ne.cur
            val nextCost = cur.cost+ne.cost

            if(nextCost > m) continue
            if(dp[nextCost][next]<= nextDis) continue

            dp[nextCost][next] = nextDis

            if(next == n) continue
            pq.add(Node(next, nextCost, nextDis))

        }
    }


}

fun main() = with(System.out.bufferedWriter()) {

    T = getInt()
    for (t in 1..T) {
        //input
        val (n, m, k) = getIntList()
        edge = Array(n + 1) { ArrayList() }
        dp = Array(m+1) { IntArray(n+1){Int.MAX_VALUE} }
        for (i in 0 until k) {
            val (from, to, cost, dis) = getIntList()
            edge[from].add(Node(to, cost, dis))
        }
        
        //solve
        dijkstra(n,m)

        //output
        var answer=Int.MAX_VALUE
        for(i in dp.indices){
//            println(dp[i][n])
            answer = answer.coerceAtMost(dp[i][n])
        }
        write("${if(answer==Int.MAX_VALUE) "Poor KCM" else answer }\n")
    }

    close()
}