백준 11779 최소비용 구하기 2

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

n개의 도시들 사이에서 m대의 버스를 통한 경로들이 있다.

A도시에서 B도시까지 가는 최소 비용과 그 경로를 구하는 문제이다.

전형적인 다익스트라 문제이며, 추가로 경로를 출력해야 한다.

분명 알고리즘 강의에서 다익스트라의 경로 추적에 대한 설명을 듣고 이해했었는데, 너무 오래되어 이 문제를 처음 풀 때 기억이 나지 않았다.

그래서 처음 이 문제를 풀 때 가변 리스트를 사용하여 경로를 갱신할 때 위치를 덧붙이고, 최소 경로를 찾았을 때 해당 경로를 따로 배열에 저장하는 방식으로 풀었다.

import java.util.*

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val m = readLine().toInt()
    val info = Array(m){readLine().split(' ').map{it.toInt()}}

    val (start, end) = readLine().split(' ').map{it.toInt()}

    val map = Array(n + 1){IntArray(n + 1){-1}}

    for(line in info) {
        if(map[line[0]][line[1]] == -1 || map[line[0]][line[1]] > line[2])
            map[line[0]][line[1]] = line[2]
    }

    fun dijkstra(): Pair<IntArray, Array<List<Int>>>{
        val distances = IntArray(n + 1){Int.MAX_VALUE}
        val paths = Array(n + 1){ listOf<Int>()}
        val pq = PriorityQueue<Vertex>{ v1, v2 -> v1.cost - v2.cost}
        distances[start] = 0
        pq.offer(Vertex(start, 0))

        while(pq.isNotEmpty()){
            val now = pq.poll()
            if(distances[now.v] < now.cost)
                continue
            for(j in 1 until map[now.v].size){
                if(map[now.v][j] != -1) {
                    val cost = now.cost + map[now.v][j]
                    if (distances[j] > cost){
                        distances[j] = cost
                        val path = now.path.toMutableList()
                        path.add(j)
                        paths[j] = path
                        pq.offer(Vertex(j, cost, path))
                    }
                }
            }
        }
        return Pair(distances, paths)
    }

    val result = dijkstra()
    println(result.first[end])
    println(result.second[end].size + 1)
    val paths = StringBuilder("$start ")
    for(p in result.second[end])
        paths.append("$p ")
    print(paths.toString())
}

data class Vertex(val v: Int, val cost: Int, val path: MutableList<Int> = mutableListOf())

처음 풀어서 통과했을 때의 코드이다.

다익스트라 알고리즘을 진행하는 함수에서 paths라는 배열을 추가로 만들어 i번째까지의 경로를 paths[i]에 저장하였다 (List<Int> 타입)

최소 경로를 갱신할 때 현재 위치(노드)까지의 경로에서 다음 위치(j)를 배열에 추가하고, paths[j]를 갱신하도록 구현하였다.

이렇게 풀이를 하긴 했으나, 아무래도 탐색할 때 마다 경로 리스트를 복사한 뒤 추가하여 노드에 넣는 방식이 메모리 측면에서 부담이 될 수 있을 것 같아 풀고난 뒤 다른 사람들의 풀이를 살펴보았다.

그리고나서 갱신할 때 이전 위치들을 저장하여 재귀적으로 경로를 추적하는 방법을 찾았고, 이 방법으로 다시 풀이해 보았다.

import java.util.*

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val m = readLine().toInt()
    val info = Array(m){readLine().split(' ').map{it.toInt()}}

    val (start, end) = readLine().split(' ').map{it.toInt()}

    val map = Array(n + 1){IntArray(n + 1){-1}}
    val paths = IntArray(n + 1){-1}

    for(line in info) {
        if(map[line[0]][line[1]] == -1 || map[line[0]][line[1]] > line[2])
            map[line[0]][line[1]] = line[2]
    }

    fun dijkstra(): IntArray{
        val distances = IntArray(n + 1){Int.MAX_VALUE}
        val pq = PriorityQueue<Vertex>{ v1, v2 -> v1.cost - v2.cost}
        distances[start] = 0
        paths[start] = 0
        pq.offer(Vertex(start, 0))

        while(pq.isNotEmpty()){
            val now = pq.poll()
            if(distances[now.v] < now.cost)
                continue
            for(j in 1 until map[now.v].size){
                if(map[now.v][j] != -1) {
                    val cost = now.cost + map[now.v][j]
                    if (distances[j] > cost){
                        distances[j] = cost
                        paths[j] = now.v
                        pq.offer(Vertex(j, cost))
                    }
                }
            }
        }
        return distances
    }

    val result = dijkstra()
    println(result[end])

    val path = mutableListOf<Int>()
    val answer = StringBuilder()
    var cur = end
    while(cur != 0){
        path.add(cur)
        cur = paths[cur]
    }
    println(path.size)
    for(i in path.size - 1 downTo 0){
        answer.append("${path[i]} ")
    }
    print(answer.toString())
}

data class Vertex(val v: Int, val cost: Int)

최소 경로를 찾아 갱신하는 부분에서 "paths[다음 위치] = 현재 위치" 부분을 추가하여 나중에 end부터 start가 나올 때까지 paths를 역순으로 탐색하여 추적하도록 하였다.

근데 의외로 메모리 사용량은 100KB밖에, 시간은 오히려 28ms가 증가하였다.

추후에 생각해보도록 하겠다.