[백준] 17835 면접보는 승범이네

 

🔒 문제

 

 

🧠 아이디어

"마을로부터 면접장 까지의 최단 거리" => 다익스트라.

V: 최대 10만

E: 최대 50만

K (면접장): 최대 10만

 

 

바로 다익스트라를 돌리면 안된다.

 

무식하게 모든 마을로부터 면접장까지의 거리를 다 구하려하면

 

$$ VE Log(E) + VK $$

 

로 시간 초과가 발생한다.

 

 

 

 

모든 면접장에서 마을까지의 거리로
각각 다익스트라를 돌려도 안된다.

면접장 -> 마을까지의 거리도 무식하게 다구하면

$$ KE Log (E) + KV$$

 

로 마찬가지로 시간초과 난다.

 

아니 이거 대체 어케해..?

따라서 마을 -> 면접장이 아닌 면접장 -> 마을까지의 최단 거리를 구하는 방식으로 접근한다.

이를 통해 다음과 같이 시간 복잡도를 줄일 수 있다.

$$ E Log(E) + V $$

 

 

여기서는 '시작 정점'이
여러개여도 된다.

  어느 면접장으로부터 어느 마을까지의 최단거리인지가 중요한게 아니고 오로지 최단거리가 업데이트 되기만 하면되기 때문이다. 또, 다익스트라는 항상 현재 만들어진 간선 정보에서 최소 간선을 선택을 하는 그리디 방식으로 동작하므로 시작정점이 여러개로 짬뽕된 상태로 돌려도 각 목적 마을까지의 모든 최단거리는 업데이트된다.

 

풀이 흐름

1. 마을 -> 면접장이 아닌 면접장 -> 마을로 간선 정보 순서 변경하여 저장
2. 시작 정점을 모든 면접장으로부터 출발
3. 업데이트된 거리정보중 최대 거리값과 index 를 출력
   단 이때, 도로의 길이 C가 최대 10만이므로 10만 * 50만 => 500억 으로 Int 최대 범위를 넘어선다
   => 거리정보를 저장할 배열을 Int 가 아닌 Long 으로 지정한다.
   
   

🔑 Kotlin Code

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.PriorityQueue

private fun dijkstra(distances: LongArray, interviewNums: List<Int>, priorityQueue: PriorityQueue<Pair<Int,Long>>, adjacentList: Array<ArrayList<IntArray>>) {
    distances[0] = 0
    interviewNums.forEach {
        distances[it] = 0
        // to & weight
        priorityQueue.add(Pair(it, distances[it]))
    }

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

        // 현재 최소라고 잡힌애의 모든 놈들을 긁으며 다음 최소를 결정한다.
        for (adjacentNode in adjacentList[minVertexNum]) {
            val (to, toWeight) = adjacentNode
            if (distances[to] <= totalWeight + toWeight.toLong()) continue
            distances[to] = totalWeight + toWeight.toLong()
            priorityQueue.add(Pair(to, distances[to]))
        }
    }

}

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (V, E, I) = br.readLine().split(" ").map(String::toInt)

    val distances = LongArray(V + 1){Long.MAX_VALUE}
    // index: from, value: (to, weight)
    val adjacentList = Array(V + 1){ArrayList<IntArray>()}
    val priorityQueue = PriorityQueue<Pair<Int, Long>>(E){ele1, ele2-> ele1.second.compareTo(ele2.second)}

    // 모든 마을은 최소 1개 이상의 면접장에 도착할 수 있다.
    // => 제시된 모든 면접장을 시작으로 모든 마을에 대해 최소 1개 이상 연결된다.
    repeat(E){
        val (from, to , weight) = br.readLine().split(" ").map(String::toInt)
        // 면접장 -> 마을까지의 거리
        adjacentList[to].add(intArrayOf(from, weight))
    }

    val interviewNums = br.readLine().split(" ").map(String::toInt)

    dijkstra(distances, interviewNums, priorityQueue, adjacentList)

    val maxDistance = distances.maxOf { it }
    val maxIdx = distances.indexOf(maxDistance)

    println(maxIdx)
    println(maxDistance)

}