백준 22865 가장 먼 곳 Kotlin (다익스트라)

문제 출처 : https://www.acmicpc.net/problem/22865

22865번: 가장 먼 곳

문제

 N개의 땅 중에서 한 곳에 자취를 하려고 집을 알아보고 있다. 세 명의 친구 A, B, C가 있는데 이 친구들의 살고 있는 집으로부터 가장 먼 곳에 집을 구하려고 한다.

이때, 가장 먼 곳은 선택할 집에서 거리가 가장 가까운 친구의 집까지의 거리를 기준으로 거리가 가장 먼 곳을 의미한다.

예를 들어, X 위치에 있는 집에서 친구 A, B, C의 집까지의 거리가 각각 3, 5, 4이라 가정하고 Y 위치에 있는 집에서 친구 A, B, C의 집까지의 거리가 각각 5, 7, 2라고 하자.

이때, 친구들의 집으로부터 땅 X와 땅 Y 중 더 먼 곳은 X 위치에 있는 집이 된다. 왜냐하면 X에서 가장 가까운 친구의 집까지의 거리는 3이고, Y에서는 2이기 때문이다.

친구들이 살고 있는 집으로부터 가장 먼 곳을 구해보자.

입력

첫번째 줄에 자취할 땅 후보의 개수 N이 주어진다.

2번째 줄에는 친구 A, B, C가 사는 위치가 공백으로 구분되어 주어진다. 이때 친구들은 N개의 땅 중 하나에 사는 것을 보장한다. (같은 위치에서 살 수 있다.)

3번째 줄에는 땅과 땅 사이를 잇는 도로의 개수 M이 주어진다.

그 다음줄부터 M+3번째 줄까지 땅 D, 땅 E, 땅 D와 땅 E와 사이를 연결하는 도로의 길이 L이 공백으로 구분되어 주어진다. 이 도로는 양뱡항 통행이 가능하다.

출력

친구들이 살고 있는 집으로부터 가장 먼 곳의 땅 번호를 출력한다. 만약 가장 먼 곳이 여러 곳이라면 번호가 가장 작은 땅의 번호를 출력한다.

제한

•  1≤N≤100,000
•  N−1≤M≤500,000
•  1≤A,B,C,D,E≤N
•  1≤L≤10,000

알고리즘 분류

• 그래프 이론
• 다익스트라

풀이

다익스트라 문제이다.

후후후

1트 만에 성공해서 기분이 좋다.

입력의 크기를 보고 당황한 것도 잠시, 냅다 문제를 거꾸로 뒤집어버렸다.

실로 엄청난 문제 해결 능력이다.

 

문제는, 친구들의 집 A,B,C에서 가장 멀리 있는 곳에 집을 짓는 것이다.

임의의 땅 X에서 A,B,C에 가장 멀리 떨어진 땅을 구하는 것은 플로이드 와샬로 쉽게 구할 수 있겠지만,

입력의 크기가 10만이기 때문에, O(V^3)의 시간복잡도인 플로이드 와샬로는 시간 초과가 난다.

 

문제를 잘 생각해 보면,

우리는 가장 먼 땅 X를 구하기 위해 모든 땅에서 친구 집 A,B,C까지의 최단 거리를 구할 필요도 없고,

마찬가지로 모든 땅에서 모든 땅으로의 최단 거리를 구할 필요도 없다.

문제를 거꾸로 생각하면, A,B,C 이 3개의 땅에서만 모든 땅에 대한 최단 거리를 구하면 된다.

 

A에서 X라는 땅에 가기 위한 최단 거리가 5

B에서 X라는 땅에 가기 위한 최단 거리가 2

C에서 X라는 땅에 가기 위한 최단 거리가 3

이라 하자.

이를 반대로 생각하면 X에서 A,B,C 땅에 가기 위한 최단거리가 5,2,3인 것이다.

이때 X와 A,B,C의 거리는 2이고, 이러한 모든 임의의 X를 구해서 최댓값을 출력하면 된다.

 

이게 전부다.

사실 별거 없다.

문제를 읽으면서 처음부터  A,B,C에서 다익스트라 3번 돌리면 되겠구나 라고 생각할 수 있다.

그냥 한 번에 통과돼서 오버 좀 했다.

 

코드

import kotlin.math.*
import java.util.*

val INF = 987654321

//1<=n<=100000 정점 갯수
//n-1<=m<=500000 간선 갯수
//1<=a,b,c,d,e,<=n 정점들
//1<=l<=10000 도로 길이
//a,b,c에서 다익스트라 총 3번
//이후 같은 칸에서 a,b,c중 최솟값들을 뽑아서 최댓갑 출력

val friends = Array(3){IntArray(100001){INF}}
val edge = Array(100001){ArrayList<Pair<Int,Int>>()}

fun dijkstra(start : Int,friendNum  : Int){
    val pq = PriorityQueue<Pair<Int,Int>>(kotlin.Comparator { a, b ->
        when{
            a.second < b.second -> -1
            a.second == b.second -> 0
            else -> 1
        }
    })
    pq.add(Pair(start,0))
    friends[friendNum][0]=0
    while(pq.isNotEmpty()){
        val cur = pq.poll()

        if(friends[friendNum][cur.first]< cur.second) continue

        for(next in edge[cur.first]){
            val nextDis = cur.second + next.second
            if(friends[friendNum][next.first]> nextDis){
                pq.add(Pair(next.first,nextDis))
                friends[friendNum][next.first] = nextDis
            }
        }
    }

}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val n = br.readLine().toInt()
    val friendPos = br.readLine().split(' ').map{it.toInt()}
    val m = br.readLine().toInt()
    for(i in 0 until m){
        val (from, to, dis) = br.readLine().split(' ').map{it.toInt()}
        edge[from].add(Pair(to,dis))
        edge[to].add(Pair(from,dis))
    }
    for(i in friendPos.indices){
        dijkstra(friendPos[i],i)
    }
    var maxDis=Pair(0,0)
    for(i in 1 .. n){
        var dis=INF
        for(j in 0 until 3){
            dis = min(friends[j][i],dis)
        }
        if(maxDis.first < dis){
            maxDis = Pair(dis,i)
        }
    }
    write("${maxDis.second}")

    close()
}