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

문제

---

생각하기

---

• Shortest Path with Path Retrieval(경로 추적 최단 경로 찾기) 유형 문제이다.

  • 다익스트라를 사용해야 한다.

동작

        for (nextNode in adjList[nowNode.node]) {
            if (dist[nextNode.node] > dist[nowNode.node] + nextNode.time) {
                dist[nextNode.node] = dist[nowNode.node] + nextNode.time
                pre[nextNode.node] = nowNode.node
                pque.offer(Node(nextNode.node, dist[nextNode.node]))
            }
        }

다익스트라를 통해서 노드별 최소 비용 경로를 찾아서 end 까지 의 최소 비용을 구하게 된다.

pre[nextNode.node] = nowNode.node로 노드별로 이전에 온 노드를 저장한다.
최소 비용의 경로를 찾으면서 자동으로 이전의 노드를 저장하면 어떤 노드를 통해서 오게 되는지 자연스럽게 갱신하면 저장된다.

    val pathList = LinkedList<Int>()
    var cur = end
    while (cur != start) {
        pathList.offerFirst(cur)
        cur = pre[cur]
    }

    pathList.offerFirst(start)
    sb.append(pathList.size).append('\n')
    while (pathList.isNotEmpty()) {
        sb.append(pathList.pollFirst()).append(' ')
    }

pathList에 역순으로 pre[cur]에 값을 cur로 저장하며 타고 타고 가서 노드 이동 경로를 저장해준다.

그리고 마지막에 end를 저장해주면 이동 경로를 알 수 있다.

결과

코드

---

Kotlin

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

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private var M = 0
private var start = 0
private var end = 0
private const val INF = Int.MAX_VALUE / 4

private lateinit var adjList: MutableList<MutableList<Node>>
private lateinit var dist: IntArray
private lateinit var pre: IntArray

private data class Node(var node: Int, var time: Int)

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

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    dijkstra()
    sb.append(dist[end]).append('\n')

    val pathList = LinkedList<Int>()
    var cur = end
    while (cur != start) {
        pathList.offerFirst(cur)
        cur = pre[cur]
    }

    pathList.offerFirst(start)
    sb.append(pathList.size).append('\n')
    while (pathList.isNotEmpty()) {
        sb.append(pathList.pollFirst()).append(' ')
    }

    return sb.toString()
} // End of solve()

private fun dijkstra() {
    val pque = PriorityQueue(compareBy<Node> { it.time })
    pque.offer(Node(start, 0))
    dist[start] = 0

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

        if (nowNode.node == end) break
        if (nowNode.time > dist[nowNode.node]) continue

        for (nextNode in adjList[nowNode.node]) {
            if (dist[nextNode.node] > dist[nowNode.node] + nextNode.time) {
                dist[nextNode.node] = dist[nowNode.node] + nextNode.time
                pre[nextNode.node] = nowNode.node
                pque.offer(Node(nextNode.node, dist[nextNode.node]))
            }
        }
    }
} // End of dijkstra()

private fun input() {
    N = br.readLine().toInt() // 도시의 개수
    M = br.readLine().toInt() // 버스의 개수

    dist = IntArray(N + 1) { INF }
    pre = IntArray(N + 1)
    adjList = ArrayList()
    repeat(N + 1) {
        adjList.add(ArrayList())
    }

    repeat(M) {
        StringTokenizer(br.readLine()).run {
            val u = nextToken().toInt()
            val v = nextToken().toInt()
            val w = nextToken().toInt()

            adjList[u].add(Node(v, w))
        }
    }

    StringTokenizer(br.readLine()).run {
        start = nextToken().toInt()
        end = nextToken().toInt()
    }
} // End of input()