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

문제

---

생각하기

---

• 다익스트라 문제이다.

• 가중치에 따라 최단시간을 구하는 것도 중요하지만, 왕이 지나는 동안 지나갈 수 없다는 점을 인지해야 한다.

  • 시간 계산을 잘해야됨

동작

    var sum = 0
    // 왕이 방문하는 구간의 시간 계산
    for (i in 0 until G - 1) {
        val s = kingVisitArr[i]
        val e = kingVisitArr[i + 1]

        goArray[s][e].start = sum
        goArray[e][s].start = sum

        goArray[s][e].end = sum + timeArr[s][e]
        goArray[e][s].end = sum + timeArr[e][s]
        sum += timeArr[s][e]
    }

왕이 방문하는 구간의 시간을 미리 계산해준다.
각 구간별로 출발지의 시간과 도착하는 곳의 시간을 timeArr 배열에 저장한다.

    val pque = PriorityQueue<Cross>()

    dist[A] = K
    pque.offer(Cross(A, K))

이동하는 시간을 가중치로 삼아서 우선순위를 매긴다. -> PriorityQueue를 사용

왕과의 시간 차이 K가 곧 상근이가 출발하는 시간을 의미하므로 dist배열의 상근이 출발 지점 A의 값을 K로 설정한다.

그리고 pque에 출발지점과 출발시간 A, K를 저장한다.

        crossList.get(pollCross.road).forEach {
            if (dist[pollCross.road] >= goArray[pollCross.road][it.road].start && dist[pollCross.road] <= goArray[pollCross.road][it.road].end) {
                dist[it.road] = goArray[pollCross.road][it.road].end + it.time
                pque.offer(Cross(it.road, dist[it.road]))
            } else {
                if (dist[it.road] > dist[pollCross.road] + it.time) {
                    dist[it.road] = dist[pollCross.road] + it.time
                    pque.offer(Cross(it.road, dist[it.road]))
                }
            }
        }

각 출발하는 지점을 기준으로 최단시간을 갱신하기 위해 출발하는 곳과 연결된 도로를 모두 탐색해서 도착지까지 최단시간으로 갱신하는 작업을 진행한다.

if문은 기존의 dist배열의 출발 시간이 현재 이동하는 구간의 출발 시간보다 크거나 같고, 출발점의 시간이 도착시간보다 작거나 같을 경우 새로운 시간으로 갱신을 하는 조건을 주었다.

else에서는 반대로 새로운 조건을 준다. 출발점에서 도착지 까지의 최단시간 + 이동시간이 도착지의 최단시간보다 작을 경우 갱신을한다.

코드

---

Kotlin

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

private const val INF = Integer.MAX_VALUE
private var N = 0
private var M = 0
private var A = 0
private var B = 0
private var K = 0
private var G = 0

private var kingVisitArr = IntArray(1001)
private var timeArr = Array(1001) { Array(1001) { 0 } }
private var goArray = Array(1001) { Array(1001) { Go() } }
private var dist = IntArray(1001) { INF }

// 인접리스트
private lateinit var crossList: ArrayList<ArrayList<Cross>>
private data class Cross(var road: Int = 0, var time: Int = 0) : Comparable<Cross> {
    override fun compareTo(other: Cross): Int {
        return time - other.time
    }
} // End of Cross class

private data class Go(var start: Int = 0, var end: Int = 0)

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt()
    M = st.nextToken().toInt()
    init()

    st = StringTokenizer(br.readLine())
    A = st.nextToken().toInt() // 상근이가 배달을 시작하는 교차로
    B = st.nextToken().toInt() // 상근이가 배달을 마치는 교차로
    K = st.nextToken().toInt() // 고둘라가 출발한 시간과 상근이가 출발 시간의 차이
    G = st.nextToken().toInt() // 고둘라가 방문하는 교차로의 개수

    st = StringTokenizer(br.readLine())
    for (i in 0 until G) {
        kingVisitArr[i] = st.nextToken().toInt()
    }

    for (i in 0 until M) {
        st = StringTokenizer(br.readLine())
        val start = st.nextToken().toInt()
        val end = st.nextToken().toInt()
        val time = st.nextToken().toInt()

        crossList[start].add(Cross(end, time))
        crossList[end].add(Cross(start, time))

        timeArr[start][end] = time
        timeArr[end][start] = time
    }

    var sum = 0
    // 왕이 방문하는 구간의 시간 계산
    for (i in 0 until G - 1) {
        val s = kingVisitArr[i]
        val e = kingVisitArr[i + 1]

        goArray[s][e].start = sum
        goArray[e][s].start = sum

        goArray[s][e].end = sum + timeArr[s][e]
        goArray[e][s].end = sum + timeArr[e][s]
        sum += timeArr[s][e]
    }

    dijkstra()
    println(dist[B] - K)
} // End of main

private fun dijkstra() {
    val pque = PriorityQueue<Cross>()
    
    dist[A] = K
    pque.offer(Cross(A, K))
    
    while (!pque.isEmpty()) {
        val pollCross = pque.poll()

        crossList.get(pollCross.road).forEach {
            if (dist[pollCross.road] >= goArray[pollCross.road][it.road].start && dist[pollCross.road] <= goArray[pollCross.road][it.road].end) {
                dist[it.road] = goArray[pollCross.road][it.road].end + it.time
                pque.offer(Cross(it.road, dist[it.road]))
            } else {
                if (dist[it.road] > dist[pollCross.road] + it.time) {
                    dist[it.road] = dist[pollCross.road] + it.time
                    pque.offer(Cross(it.road, dist[it.road]))
                }
            }
        }
    }

} // End of dijkstra

private fun init() {
    crossList = ArrayList()
    for (i in 0 until N + 1) {
        crossList.add(ArrayList())
    }
} // End of init