백준 1277 발전소 설치 Kotlin (다익스트라)

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

1277번: 발전소 설치

문제

엄청난 벼락을 맞아 많은 전선들이 끊어져 현재 전력 공급이 중단된 상태이다. 가장 심각한 문제는 1번 발전소에서 N번 발전소로 가는 중간의 전선이 끊어진 것이기에 일단 이 두 발전소를 다시 연결하는게 현재 해결해야할 첫 번째 과제이다.

발전소는 1번부터 N번까지 번호로 매겨져 2차원 격자 좌표 위에 있다. 그리고 몇몇 전선은 보존된 채 몇몇 발전소를 잇고 있다. 문제는 현재 전선과 발전소의 위치가 주어졌을 때 최소의 전선 길이를 추가로 사용하여 1번 발전소와 N번 발전소를 연결짓는 것이다. 물론 연결 짓는 중간에 다른 발전소를 거쳐갈 수 있다. 단, 안정성 문제로 어떠한 두 발전소 사이의 전선의 길이가 M을 초과할 수는 없다. 아래에 이에 대한 예를 그려놓았다.

         연결 전                          연결 후

3  . . . 7 9 . . . . .          3  . . . 7 9 . . . . .
                                          /
2  . . 5 6 . . . . . .          2  . . 5 6 . . . . . .
                                        /
1  2-3-4 . 8 . . . . .          1  2-3-4 . 8 . . . . .
   |                               |
0  1 . . . . . . . . .          0  1 . . . . . . . . .

   0 1 2 3 4 5 6 7 8 9             0 1 2 3 4 5 6 7 8 9

입력

첫 줄에는 발전소의 수 N(1 ≤ N ≤ 1,000)과 현재 남아있는 전선의 수 W(1≤ W ≤ 10,000)가 주어진다. 두 번째 줄에는 제한 길이 M(0.0 < M < 200,000.0)가 주어진다. 다음 N개의 줄에는 1번 발전소부터 N번 발전소까지 각각의 발전소의 X좌표와 Y좌표(-100,000 ≤ xi,yi  ≤ 100,000)가 차례대로 주어진다. 다음 W개의 줄에 대해 각 줄에는 두 개의 정수가 입력되어지는데 이는 현재 남아있는 전선이 잇고 있는 두 발전소를 의미한다.

출력

첫 줄에 1번 발전소와 N번 발전소를 잇는데 필요한 추가 전선 길이의 최솟값을 1000배하여 출력한다. (단, 1000배하고 난 후 나머지 소수는 반올림이 아닌 버림을 한다)

알고리즘 분류

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

풀이

다익스트라 문제이다.

문제를 크게 꼬진 않았지만, 간선을 따로 주지 않고, 주어진 정점들로 피타고라스 정의를 이용해 간선의 길이를 직접 구해야 하는 점이 번거롭다면 번거로운 점이다.

 

일반적인 다익스트라 알고리즘에서 다음 부분들만 추가해 주면 된다.

1. 보존된 발전소를 넘어갈 때는 가중치를 0으로 바꾸었으며, 이러한 발전소는 다익스트라 알고리즘 상 한 번만

   방문하게 된다.

2. 가중치 제한 M이 주어진다. 간선의 가중치가 M을 초과하는 경우 정점을 방문하지 않고 스킵한다.

3. 정점들 간의 거리(간선의 가중치)를 구하는 것은 다익스트라의 while 문 내부에서 그때그때 구해줬다.

 

 

코드

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

fun dijkstra(n : Int, limit : Double, graph : Array<Pair<Long,Long>>, connected : Array<BooleanArray>, visited : DoubleArray) : Long{

    val pq = PriorityQueue<Pair<Double,Int>>(kotlin.Comparator {a, b ->
        when{
            a.first < b.first -> -1
            a.first == b.first -> 0
            else -> 1
        }

    })
    pq.add(Pair(.0,0))
    visited[0]=.0
    while(pq.isNotEmpty()){
        val cur = pq.poll()
        //이미 최소값으로 갱신되어있다면 스킵
        if(visited[cur.second]<cur.first) continue
        //모든 정점에 대한 거리 삽입
        for(i in 0 until n){
            //본인에서 본인으로 가는 경우는 스킵
            if(i==cur.second)continue
            var nextDis = sqrt(
                ((graph[i].first - graph[cur.second].first)*(graph[i].first - graph[cur.second].first)+
                        (graph[i].second - graph[cur.second].second)*(graph[i].second - graph[cur.second].second)).toDouble()
            )
            //문제에서 주어진 연결되어있는 발전소는 가중치 0
            if(connected[cur.second][i]) nextDis=.0
            //visited에는 초기값으로 Long.MAX_VALUE들어있음
            //따라서 문제에서 주어진 연결되어있는 발전소는 한 번만 탐색하고 이후로는 탐색 x
            if(visited[i]<=cur.first+nextDis) continue
            
            //제한 길이를 넘으면 스킵
            if(nextDis>limit) continue
            
            pq.add(Pair(cur.first+nextDis,i))
            visited[i]=cur.first+nextDis
        }
    }
    //Long으로 변환하면서 자동으로 floor
    return (visited[n-1]*1000).toLong()
}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val (n,w) = br.readLine().split(' ').map{it.toInt()}
    val limit = br.readLine().toDouble()
    val graph = Array(n){Pair(0L,0L)}
    val connected = Array(n){BooleanArray(n)}
    for(i in 0 until n){
        val (x,y) = br.readLine().split(' ').map{it.toLong()}
        graph[i] = Pair(x,y)
    }
    for(i in 0 until w){
        val (from, to) = br.readLine().split(' ').map{it.toInt()}
        connected[from-1][to-1] = true
        connected[to-1][from-1]=true
    }
    
    //두 점 사이의 거리는 Int 범위를 벗어나지 않음
    val visited = DoubleArray(n){Int.MAX_VALUE.toDouble()}
    write("${dijkstra(n,limit,graph,connected,visited)}")
    close()
}