[백준/BOJ] 1504번: 특정한 최단 경로

문제

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

1504번: 특정한 최단 경로

해설

다익스트라 알고리즘을 응용하는 문제이다.

문제에는 다음과 같은 조건이 있다.

• 임의로 주어진 두 정점은 반드시 통과해야 한다.
• 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다.

주어진 두 정점을 거쳐야 하는 최단 경로를 구해야 한다.

간단히 생각해보면, 다음과 같다.

1. 1 -> v1 -> v2 -> n
2. 1 -> v2 -> v1 -> n

이를 분리시켜서 각각의 최소 비용을 구하고 합해주면 최단거리가 나오게 되는 것이다.

즉 1번의 경우

1. 1 -> v1
2. v1 -> v2
3. v2 ->n

의 최소비용을 각각 구해준다. 다익스트라 알고리즘을 총 3번 수행하는 것이다.

2번 또한 마찬가지로 구해준다.

둘 중 더 작은 값이 최소 비용이 된다.

 

주의할 점은 초기 비용 배열을 Int.MAX_VALUE로 해주면 오버플로우가 발생하게 되어 틀렸습니다가 뜬다.

간선의 최대 개수가 200,000이고, 비용의 최대값이 1,000이므로 초기비용의 배열을 200,000,000으로 초기화해주면 된다.

소스 코드

import java.util.*
import kotlin.collections.ArrayList

private lateinit var graph: Array<ArrayList<Pair<Int, Int>>>

data class Info(val node: Int, val cost: Int): Comparable<Info> {
    override fun compareTo(other: Info): Int = cost - other.cost
}

fun main() = with(System.`in`.bufferedReader()) {
    val (n, e) = readLine().split(" ").map { it.toInt() }

    graph = Array(n + 1) { ArrayList<Pair<Int, Int>>() }

    repeat(e) {
        val (from, to , cost) = readLine().split(" ").map { it.toInt() }
        graph[from].add(Pair(to, cost))
        graph[to].add(Pair(from, cost))
    }

    val (v1, v2) = readLine().split(" ").map { it.toInt() }
    var temp1 = dijkstra(n, 1, v1)
    temp1 += dijkstra(n, v1, v2)
    temp1 += dijkstra(n, v2, n)

    var temp2 = dijkstra(n, 1, v2)
    temp2 += dijkstra(n, v2, v1)
    temp2 += dijkstra(n, v1, n)

    val ans = minOf(temp1, temp2)

    if(ans >= 200000000) println(-1)
    else println(ans)
}

private fun dijkstra(n: Int, start: Int, end: Int): Int {
    val visited = BooleanArray(n + 1) { false }
    val cost = IntArray(n + 1) { 200000000 }

    val pq = PriorityQueue<Info>()
    pq.add(Info(start, 0))
    cost[start] = 0

    while(pq.isNotEmpty()) {
        val cur = pq.poll()
        val curNode = cur.node
        val curCost = cur.cost

        if(curNode == end) break

        if(!visited[curNode]) {
            visited[curNode] = true

            for(i in graph[curNode].indices) {
                val nextNode = graph[curNode][i].first
                val nextCost = curCost + graph[curNode][i].second

                if(!visited[nextNode] && nextCost < cost[nextNode]) {
                    cost[nextNode] = nextCost
                    pq.add(Info(nextNode, nextCost))
                }
            }
        }
    }

    return cost[end]
}