BOJ_1504_특정한 최단 경로

문제

풀이

package solve_1504

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

private const val INF = 200000001

private lateinit var graph: Array<LinkedList<Edge>>

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }

    val n = input()
    val e = input()

    graph = Array(n + 1) {
        LinkedList<Edge>()
    }


    repeat(e) {
        val a = input()
        val b = input()
        val c = input()
        graph[a].add(Edge(b, c))
        graph[b].add(Edge(a, c))
    }

    val v1 = input()
    val v2 = input()

    val startOne = dijkstra(1)
    val startV1 = dijkstra(v1)
    val startV2 = dijkstra(v2)

    val answer1 = startOne[v1] + startV1[v2] + startV2[n]
    val answer2 = startOne[v2] + startV2[v1] + startV1[n]

    val answer = minOf(answer1, answer2)

    if(answer >= INF) {
        println(-1)
    } else{
        println(answer)
    }

}

private fun dijkstra(start: Int): IntArray {
    val queue = PriorityQueue<Edge>()
    val distance = IntArray(graph.size) {
        INF
    }
    distance[0] = 0
    distance[start] = 0
    queue.add(Edge(start, 0))

    while (queue.isNotEmpty()) {
        val (node, dist) = queue.poll()

        if(distance[node] < dist) continue
        graph[node].forEach{
            val nextNode = it.end
            val nextDist = dist + it.dist

            if(nextDist < distance[nextNode]) {
                distance[nextNode] = nextDist
                queue.add(Edge(nextNode, nextDist))
            }
        }
    }
    return distance
}

private data class Edge(
    val end: Int,
    val dist: Int,
) : Comparable<Edge> {
    override fun compareTo(other: Edge) = dist - other.dist

}

사용 알고리즘

다익스트라 최단경로 탐색

문제에서 주어진 2개의 정점은 무조건 거치고 1번 노드에서 n번 노드로 가는 최단 경로를 구하는 문제였다.
따라서
출발지 -> 정점1 -> 정점2 -> n 또는 출발지 -> 정점2 -> 정점1 -> n
의 경우로 정리할 수 있다. 그사이에 어떤 점을 거쳤더라도 최단 거리를 구하는 문제이기 때문에 고려할 필요가 없기 때문이다.

필요한 4개의 정점에서만 각각의 점까지의 최단경로가 필요했기 때문에 모든 정점사이의 거리를 구하는 플루이드워셜 대신 다익스트라 알고리즘을 사용했다.

시작 노드와 연결된 모든 정점들의 거리를 비교하여 업데이트 시켜주고 방문한다.
방문한 노드에서 연결된 간선들 중 우선순위 큐를 사용해 가장 짧은 간선을 선택후 이동한다.
마찮가지로 해당 노드또한 방문처리를 하고 그 노드를 거쳐 계산되는 거리를 비교하여 업데이트 시킨다.
이렇게 모든 점에 대해 방문이 확인되었다면 출발 노드로 부터의 최단거리를 구할 수 있다.