백준 10217번
https://www.acmicpc.net/problem/10217

문제

---

생각하기

---

• 다익스트라와 DP가 섞인 문제이다.

• 최적화를 고려하지 않으면 풀 수 없는 문제이다.
  • memo[공항][비용] = time으로 저장해서 메모이제이션을 구현해야 한다.
  • 일반적인 다익스트라의 dist배열에 메모이제이션을 적용해야 한다.
  • 다익스트라 구현 안에서도 가지치기를 조금씩 해야 한다.
• 인접리스트를 통해서 구현했다.

동작

    for (i in 0..M) {
        memo[1][i] = 0
    }

출발지인 인천에서 1번에서 각 비용의 시작은 모두 0으로 초기화해둔다.

	if (ans <= memo[poll.arrivalAirport][poll.cost]) continue

가지치기로 이미 ans값 보다 큰 memo의 시간과 비용을 가지는 곳은 굳이 방문할 필요가 없으므로 가지 않는다.

	if (cost > M) continue
    
	val time = memo[poll.arrivalAirport][poll.cost] + next.time // 다음 공항으로 이동하는 데 걸리는 시간
	if (ans <= time) continue // ans 보다 시간이 클 경우 방문할 필요가 없으므로 지나침

비용이 M을 초과할 경우도 방문할 수 없으므로 지나친다.

또한 다음 공항까지 가는데 걸리는 시간을 계산 해서 time에 저장하고 만약 time이 ans보다 크거나 같으면 굳이 방문하지 않아도 되는 경우이므로 지나친다.

            if (time < memo[next.arrivalAirport][cost]) {
                if (memo[next.arrivalAirport][cost] == INF) {
                    pque.offer(Airport(next.arrivalAirport, cost, time))
                }
                memo[next.arrivalAirport][cost] = time
            }

이 문제 다익스트라 PriorityQueue while문 핵심은 계산된 시간인 time이 현재 저장되어 있는 memo의 값보다 작을 경우, memo의 값을 갱신하고, memo의 값이 INF일 경우에만 pque에 offer()를 하여 다익스트라를 진행하는 것이다.

코드

---

Kotlin

import java.io.*
import java.util.*

// input
private lateinit var br: BufferedReader

// variables
private var N = 0 // 공항의 수
private var M = 0 // 총 지원비용
private var K = 0 // 티켓정보의 수
private const val INF = Int.MAX_VALUE
private var ans = 0

private lateinit var memo: Array<IntArray> // memo[공항(노드)[비용(cost)] <- time이 저장됨
private lateinit var adjList: MutableList<MutableList<Airport>>

private data class Airport(var arrivalAirport: Int, var cost: Int, var time: Int) : Comparable<Airport> {
    override fun compareTo(other: Airport): Int {
        return cost - other.cost
    }
}

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val sb = StringBuilder()

    var T = br.readLine().toInt()
    while (T-- > 0) {
        input()

        dijkstra()

        if (ans == INF) {
            sb.append("Poor KCM").append('\n')
        } else {
            sb.append(ans).append('\n')
        }
    }

    bw.write(sb.toString())
    bw.close()
} // End of main

private fun dijkstra() {
    val pque = PriorityQueue<Airport>()
    pque.offer(Airport(1, 0, 0)) // 도착공항, 비용, 시간

    while (pque.isNotEmpty()) {
        val poll = pque.poll()

        if (ans <= memo[poll.arrivalAirport][poll.cost]) continue

        for (next in adjList[poll.arrivalAirport]) {
            val cost = poll.cost + next.cost
            
            // 비용이 M을 넘어설 경우 갈 수 없으므로 지나친다.
            if (cost > M) continue

            val time = memo[poll.arrivalAirport][poll.cost] + next.time // 다음 공항으로 이동하는 데 걸리는 시간
            if (ans <= time) continue // ans 보다 시간이 클 경우 방문할 필요가 없으므로 지나침

            if (next.arrivalAirport == N) {
                ans = time
                continue
            }

            if (time < memo[next.arrivalAirport][cost]) {
                if (memo[next.arrivalAirport][cost] == INF) {
                    pque.offer(Airport(next.arrivalAirport, cost, time))
                }
                memo[next.arrivalAirport][cost] = time
            }
        }
    }
} // End of dijkstra

private fun input() {
    var st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt()
    M = st.nextToken().toInt()
    K = st.nextToken().toInt()
    ans = INF

    adjList = ArrayList()
    memo = Array(N + 1) { IntArray(M + 1) { INF } }

    for (i in 0..N) {
        adjList.add(ArrayList())
    }

    for (i in 0..M) {
        memo[1][i] = 0
    }


    while (K-- > 0) {
        st = StringTokenizer(br.readLine())
        val u = st.nextToken().toInt() // 티켓의 출발 공항
        val v = st.nextToken().toInt() // 도착 공항
        val c = st.nextToken().toInt() // 비용
        val d = st.nextToken().toInt() // 소요시간

        adjList[u].add(Airport(v, c, d))
    }
} // End of input