백준 20007 떡 돌리기 Kotlin (다익스트라)

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

20007번: 떡 돌리기

문제

군인인 성현이는 전역 후에 새 집으로 이사를 갔다. 주변 이웃과 친하게 지내고 싶은 마음에 이웃집에 떡을 돌리기로 했다. 떡은 한번에 하나씩만 들고 갈 수 있다. 집들 사이에는 총 M개의 양방향 도로가 있다. 귀찮은 성현이는 하루에 X보다 먼 거리를 걷지 않고 거리가 가까운 집부터 방문한다. 또 잠은 꼭 본인 집에서 자야 하므로 왕복할 수 없는 거리는 다음날 가기로 다짐한다. N-1개의 이웃집 모두에게 떡을 돌리기 위해서는 최소 며칠이 소요될 것인가.

집의 번호는 0번부터 N-1번까지 차례대로 붙어있다.

입력

첫째줄에 N, M, X, Y가 공백으로 구분되어 입력된다. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000, 1 ≤ X ≤ 10,000,000, 0 ≤ Y < N)

두번째 줄부터 M+1번째 줄까지 A와 B 그리고 A집과 B집 사이의 도로의 길이 C가 주어진다. (0 ≤ A,B < N, 1 ≤ C ≤ 10,000) 단, A와 B는 서로 다른 수이고, C는 정수이다.

단, A집과 B집을 연결하는 도로는 유일하다.

출력

성현이의 집을 Y 라고 할 때, 이웃집 모두에 떡을 돌리기 위한 최소 일을 출력한다. 만약 모두 방문할수 없으면 -1을 출력한다.

알고리즘 분류

• 그래프 이론
• 데이크스트라

풀이

다익스트라 문제다.

하루에 X보다 먼 거리를 걷지 않고 거리가 가까운 집부터 방문한다

거리가 가까운 집부터 방문하는 것이 핵심이다.

A에서 B로 가는 경로중에 최단 거리를 다익스트라로 구해서 dp[B]에 저장해 놓는다.

위 방식으로 시작점에서 다른 모든 집에 대해 최단 거리를 저장한다.

거리가 가까운 집부터 방문해야 하기 때문에 정렬하고, 반복문을 돌리며 하루에 X이하로 갈 수 있는 집들을 방문하여 총 며칠이 걸리는지 계산한다.

 

 

코드

import java.util.*
val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

lateinit var edge: Array<ArrayList<Pair<Int, Int>>>
lateinit var dp: IntArray

fun dijkstra(start: Int) {
    val pq = PriorityQueue<Pair<Int, Int>> { a, b ->
        when {
            a.second < b.second -> -1
            a.second == b.second -> 0
            else -> 1
        }

    }
    dp[start] = 0
    pq.add(Pair(start, 0))

    while (pq.isNotEmpty()) {
        val cur = pq.poll()
        if (dp[cur.first] < cur.second) continue
        for (next in edge[cur.first]) {
            var (nextNum, nextDis) = next
            nextDis += cur.second
            if (dp[nextNum] <= nextDis) continue
            dp[nextNum] = nextDis
            pq.add(Pair(nextNum, nextDis))
        }
    }
}

fun findAnswer(n: Int, x: Int): Int {

    if(dp[n-1]*2>x){
        return -1
    }
    var idx = 0
    var sum = 0
    var answer = 0
    while(idx < n){
        while(idx < n && sum + dp[idx]*2 <= x){
            sum += dp[idx++]*2
        }
        sum = 0
        answer++
    }

    return answer
}

fun main() = with(System.out.bufferedWriter()) {
    //input
    val (n, m, x, y) = getIntList()
    edge = Array(n) { ArrayList() }
    dp = IntArray(n) { Int.MAX_VALUE }
    repeat(m) {
        val (from, to, dis) = getIntList()
        edge[from].add(Pair(to, dis))
        edge[to].add(Pair(from, dis))
    }

    //solve
    dijkstra(y)
    dp.sort()
    write("${findAnswer(n,x)}")

    close()
}