[백준/BOJ] 1238번: 파티

문제

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

1238번: 파티

해설

문제의 핵심을 찾아보면 다음과 같다.

1. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다.
2. 최단 시간에 오고 가기를 원한다.
3. 단방향이기 때문에 오고 가는 길이 다를지도 모른다.

최단 시간을 구하는 문제이기에 다익스트라 알고리즘을 이용하면 된다.

파티를 갔다가, 다시 집에 돌아오는 시간까지 계산해야 하기 때문에, 각 노드 당 2번의 다익스트라 알고리즘을 수행해줘야 한다. (집 -> 파티의 최단 시간, 파티 -> 집의 최단 시간)

이 중 가장 오래 걸리는 사람을 구해야 하므로, 우선순위 큐를 선언하여 내림차순으로 정렬시켜준 후, 맨 위의 값을 출력시켜주면 된다.

소스 코드

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

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

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

    val graph = Array(n + 1) { ArrayList<Pair<Int, Int>>() }
    repeat(m) {
        val (from, to, time) = readLine().split(" ").map { it.toInt() }
        graph[from].add(Pair(to, time))
    }

    val totalTime = PriorityQueue<Int>(reverseOrder())
    for(i in 1 .. n) {
        var total = dijkstra(n, i, x, graph)
        total += dijkstra(n, x, i, graph)
        totalTime.add(total)
    }

    println(totalTime.poll())
}

private fun dijkstra(n: Int, start: Int, end: Int, graph: Array<ArrayList<Pair<Int, Int>>>): Int {
    val time = IntArray(n + 1) { Int.MAX_VALUE }
    time[start] = 0

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

    while(pq.isNotEmpty()) {
        val cur = pq.poll()
        val curNode = cur.node
        val curTime = cur.time

        if(curNode == end) break

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

            if(nextTime < time[nextNode]) {
                time[nextNode] = nextTime
                pq.add(Info(nextNode, nextTime))
            }
        }
    }

    return time[end]
}