[백준] 특정한 최단 경로 (1504)(Kotlin)

원본 문제

문제 설명

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

입출력 예제1

입력	출력
4 6 1 2 3 2 3 3 3 4 1 1 3 5 2 4 5 1 4 4 2 3	7

문제 풀이1 (Dijkstra - Adjacency List)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

var adjList: Array<PriorityQueue<Node>> = arrayOf()
var route: Array<IntArray> = arrayOf()

data class Node(val index: Int, val distance: Int): Comparable<Node> {
    override fun compareTo(other: Node): Int {
        return this.distance - other.distance
    }
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {

    val (vertex: Int, edge: Int) = readLine()
        .split(" ")
        .map { it.toInt() }

    adjList = Array(vertex) { PriorityQueue<Node>() }
    route = Array(vertex) { IntArray(vertex) { Int.MAX_VALUE } }

    for (i in 0 until edge) {
        val (start: Int, dest: Int, distance: Int) = readLine()
            .split(" ")
            .map { it.toInt() }

        if (adjList[start - 1].any { it.index == dest - 1 }) {
            val oldRoad = adjList[start - 1]!!.find { it.index == dest - 1 }
            if (oldRoad!!.distance < distance) continue
        }
        adjList[start - 1].add(Node(dest - 1, distance))
        adjList[dest - 1].add(Node(start - 1, distance))
    }

    val (via1: Int, via2: Int) = readLine()
        .split(" ")
        .map { it.toInt() - 1 }


    dijkstra(intArrayOf(0, via1, via2, vertex - 1), vertex)

    val way1 = search(via1, via2, vertex - 1)
    val way2 = search(via2, via1, vertex - 1)

    if (way1 == -1 && way2 == -1)
        println(-1)
    else if (way1 == -1 || way2 == -1)
        println(Math.max(way1, way2))
    else
        println(Math.min(way1, way2))


}

fun search(stop1: Int, stop2: Int, stop3: Int): Int {

    if (route[0][stop1] == Int.MAX_VALUE) return -1
    if (route[stop1][stop2] == Int.MAX_VALUE) return -1
    if (route[stop2][stop3] == Int.MAX_VALUE) return -1

    return route[0][stop1] + route[stop1][stop2] + route[stop2][stop3]

}


fun dijkstra(routeInfo: IntArray, vertex: Int) {

    for (i in routeInfo.indices) {

        val queue: PriorityQueue<Node> = PriorityQueue()
        queue.add(Node(routeInfo[i], 0))

        var check: BooleanArray = BooleanArray(vertex) { false }

        route[routeInfo[i]][routeInfo[i]] = 0

        while (queue.isNotEmpty()) {

            val now: Int = queue.poll().index

            if (check[now]) continue
            check[now] = true

            for (next in adjList[now]) {
                if (route[routeInfo[i]][next.index] > route[routeInfo[i]][now] + next.distance) {
                    route[routeInfo[i]][next.index] = route[routeInfo[i]][now] + next.distance
                    queue.add(Node(next.index, route[routeInfo[i]][next.index]))
                }
            }
        }
    }
}