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

 

🔒 문제

 

 

🧠 아이디어

반드시 2개의 정점을 경유해서 가야하므로 

Way point (경유지) 1, 2 가 존재할 때 선택할 수 있는 경로는 다음 2가지로 좁혀진다.

출발 노드 -> 경유지 1 -> 경유지 2 -> 목적지

출발 노드 -> 경유지 2 -> 경유지 1 -> 목적지

 

여기서 구해야 할 값은 다음 5가지다.

• 출발 노드 -> 경유지 1의 최단경로
• 출발 노드 -> 경유지 2의 최단경로
• 경유지 1 ->  목적지의 최단경로
• 경유지 2 -> 목적지의 최단경로
• 경유지 1 - 경유지2 의 최단경로
  양방향 그래프기 때문에 경유지 1-> 경유지 2, 경유지 2-> 경유지1는 서로 거리가 같기 때문에 한 번만 구하면 된다.

최단 경로를 구해야하므로 Dijkstra 알고리즘 사용한다.

출발 노드 -> 경유지 1,2 는 한번에 구할 수 있고

경유지 1-> 목적지, 경유지 2-> 목적지, 경유지 1-> 경유지2

즉 총 4번의 다익스트라 알고리즘을 돌려서 아래 2가지 경로 중 더 적은 경로값을 반환하는 값을 출력하면 된다.

출발 노드 -> 경유지 1 -> 경유지 2 -> 목적지

출발 노드 -> 경유지 2 -> 경유지 1 -> 목적지

 

실수하기 쉬운 포인트

⚠️ 다익스트라 반복 중간 중간에 거리를 저장하는 배열을 초기화 줘야한다.

⚠️ 경로 중간에 Int.MAX_VALUE (경로가 존재하지 않는 경우) -1 을 출력해야한다.

배열을 생성해서 하나라도 경로가 끊겼으면 -1 을 출력

 

 

 

 

🔑 Kotlin Code

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.min

// minimum weight has max priority
val priorityQueue = PriorityQueue<IntArray>() {arr1, arr2-> arr1[1].compareTo(arr2[1])}

private fun dijkstra(startNode: Int, adjacentList: Array<LinkedList<IntArray>>, distances: Array<Int>) {

    distances[startNode] = 0
    priorityQueue.add(intArrayOf(startNode, distances[startNode]))

    while (priorityQueue.isNotEmpty()) {
        val (curNode, totalWeight) = priorityQueue.poll()
        if (distances[curNode] != totalWeight) continue

        // 인접한 노드를 모두 방문하며
        // 다음 경로가 현재 정해진 경로보다 짧은지 확인
        for (nextNode in adjacentList[curNode]) {
            val (to, weight) = nextNode
            if (distances[to] <= totalWeight + weight) continue
            distances[to] = totalWeight + weight
            priorityQueue.add(intArrayOf(to, distances[to]))
        }

    }

}

fun main(){
    // way point 1, 2 가 있을 때
    // 목적지는 다음 2케이스

    // way point 1 까지의 거리 + 1-2 사이의 거리 + way point 2 부터 목적지 까지의 최단거리
    // way point 2 까지의 거리 + 1-2 사이의 거리 + way point 1부터 목적지 까지의 최단거리

    val bufferedReader = BufferedReader(InputStreamReader(System.`in`))
    val (V, E) = bufferedReader.readLine().split(" ").map(String::toInt)

    // index: from, value: [to, weight]
    val adjacentList = Array(V + 1){ LinkedList<IntArray>() }
    val distances = Array(V + 1){Int.MAX_VALUE}

    repeat(E){_->
        val (from, to, weight) = bufferedReader.readLine().split(" ").map(String::toInt)
        // undirected graph
        adjacentList[from].add(intArrayOf(to, weight))
        adjacentList[to].add(intArrayOf(from, weight))
    }


    val (wayPoint1, wayPoint2) = bufferedReader.readLine().split(" ").map(String::toInt)

    dijkstra(1, adjacentList, distances)
    // 1 번 정점으로부터 경유지 1, 2 까지의 거리
    val toWayPoint1 = distances[wayPoint1]
    val toWayPoint2 = distances[wayPoint2]

    Arrays.fill(distances, Int.MAX_VALUE)
    dijkstra(wayPoint1, adjacentList, distances)

    // waypoint 1 - 2 사이 거리
    val distanceBetweenWayPoint = distances[wayPoint2]
    // waypoint 1 -> 목적지 거리
    val wayPoint1ToDestination = distances[V]

    Arrays.fill(distances, Int.MAX_VALUE)
    dijkstra(wayPoint2, adjacentList, distances)
    // waypoint 2 -> 목적지 거리
    val wayPoint2ToDestination = distances[V]

    // 중간에 경로가 없는 경우가 발생하면
    if (toWayPoint1 == Int.MAX_VALUE || toWayPoint2 == Int.MAX_VALUE ||
        distanceBetweenWayPoint == Int.MAX_VALUE ||
        wayPoint1ToDestination == Int.MAX_VALUE || wayPoint2ToDestination == Int.MAX_VALUE
    ) {
        print(-1)
        return
    }

    // 출발 노드 -> 경유지 1 -> 경유지 2 -> 목적지
    val way1 = toWayPoint1 + distanceBetweenWayPoint + wayPoint2ToDestination
    // 출발 노드 -> 경유지 2 -> 경유지 1 -> 목적지
    val way2 = toWayPoint2 + distanceBetweenWayPoint + wayPoint1ToDestination

    print(min(way1, way2))

}