[알고리즘] 파티 (백준 1238번)

1238번: 파티

 최단 시간만에 X번까지 왕복하는 시간을 구해야한다. 즉 각 마을에서 X번까지의 최단 시간, X번에서 각 마을까지의 최단 시간을 둘 다 구해야한다. 가장 쉽게 생각할 수 있는 방법은 플로이드 와샬로 모든 구간의 최단 시간을 구하는 것이다. 시간이 오래 걸리지만 풀긴 풀 수 있는 것 같다. (사실 1000의 3제곱이면 10억인데 못 풀 거라 생각했는데 풀긴 풀더라...)

 

 하지만 X번까지의 왕복 정보 외에는 다른 정보들은 필요가 없다. 불필요한 연산 수가 많아지기에 가장 최적화 된 방법은 다익스트라를 2번 돌리는 것이다. 간선 방향을 거꾸로한 역그래프를 하나 더 만들어서 탐색을 하면 각 마을에서 X번까지 오는 데 걸리는 최단 시간들을 구할 수 있다.

 

Solution

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

import java.util.*
import kotlin.collections.ArrayList
import kotlin.math.E
import kotlin.math.max

var br = BufferedReader(InputStreamReader(System.`in`))
var bw = BufferedWriter(OutputStreamWriter(System.out))

var N = 0
var M = 0
var X = 0
val INF = 1000001
var graph = ArrayList<ArrayList<Edge>>()
var reverse_graph = ArrayList<ArrayList<Edge>>()
lateinit var dist : IntArray
lateinit var reverse_dist : IntArray

fun solution() {

    var strtok = StringTokenizer(br.readLine())
    N = strtok.nextToken().toInt()
    M = strtok.nextToken().toInt()
    X = strtok.nextToken().toInt()//출발점

    dist = IntArray(N + 1, {INF})
    dist[X] = 0

    reverse_dist = IntArray(N + 1, {INF})
    reverse_dist[X] = 0

    for(i in 0..N)
    {
        graph.add(ArrayList())
        reverse_graph.add(ArrayList())
    }

    for(i in 0 until M)
    {
        var strtok = StringTokenizer(br.readLine())
        var from = strtok.nextToken().toInt()
        var to = strtok.nextToken().toInt()
        var weight = strtok.nextToken().toInt()

        graph.get(from).add(Edge(from, to, weight))
        reverse_graph.get(to).add(Edge(to, from, weight))
    }

    //x번에서 각 마을까지 가는 비용
    dijkstra()
    //각 마을에서 x번까지 가는 비용
    reverse_dijkstra()

    var max = 0
    for(i in 1..N)
    {
        max = max(max, dist[i] + reverse_dist[i])
    }
    bw.write(max.toString())
}

fun dijkstra()
{
    var queue = PriorityQueue<Node>(kotlin.Comparator { o1, o2 -> o1.distance - o2.distance })
    queue.offer(Node(X, 0))
    var visited = BooleanArray(N + 1)

    while(!queue.isEmpty())
    {
        var now = queue.poll()

        if(visited[now.num])
            continue
        visited[now.num] = true

        for(i in 0 until graph[now.num].size)
        {
            var edge = graph[now.num][i]

            if(dist[edge.to] > dist[now.num] + edge.weight)
            {
                dist[edge.to] = dist[now.num] + edge.weight
                queue.offer(Node(edge.to, dist[edge.to]))
            }
        }
    }
}

fun reverse_dijkstra()
{
    var queue = PriorityQueue<Node>(kotlin.Comparator { o1, o2 -> o1.distance - o2.distance })
    queue.offer(Node(X, 0))
    var visited = BooleanArray(N + 1)

    while(!queue.isEmpty())
    {
        var now = queue.poll()

        if(visited[now.num])
            continue
        visited[now.num] = true

        for(i in 0 until reverse_graph[now.num].size)
        {
            var edge = reverse_graph[now.num][i]

            if(reverse_dist[edge.to] > reverse_dist[now.num] + edge.weight)
            {
                reverse_dist[edge.to] = reverse_dist[now.num] + edge.weight
                queue.offer(Node(edge.to, reverse_dist[edge.to]))
            }
        }
    }
}

data class Edge(var from : Int, var to : Int, var weight : Int)
data class Node(var num : Int, var distance : Int)


fun main() {
    solution()
    br.close()
    bw.close()
}

 마지막에 왕복 비용 중 가장 큰 값을 출력하면 끝이다.