백준 [1446] kotlin

[문제]

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

1446번: 지름길

[풀이]

지름길 배열을 우선순위 큐에 저정을 한다 (시작점 기준으로)

이동한 거리를 저장해두는 배열을 고속도로의 길이 D 크기만큼 생성해준다. 이때 초기값을 아래과 같이 설정해준다.

var arr = IntArray(D+1){i -> i}

우선순위 큐에서 값을 하나씩 꺼내어서 값이 없을 때까지 다음 과정을 반복한다.

1.  끝에서 시작을 뺀 거리가 지름길의 거리보다 클 경우에 아래 과정은 스킵한다.

2. 이동거리를 저장한 배열 arr[끝]이 arr[시작] + 지름길거리 보다 크다면,

     2-1. 끝부터 D까지 새롭게 값을 갱신한다. 이 때 값은 기존의 값보다 arr[끝]이 arr[시작] + 지름길거리 + 현재 거리 - 끝이 작다면 갱신

 

위 과정을 코드로 나타내면 아래와 같다.

while (pq.isNotEmpty())
{
    val p = pq.poll()
    if(p.end <= D) {
        if(p.end - p.start <= p.distance) continue
        if(arr[p.end] > arr[p.start] + p.distance){
            val dist = arr[p.start] + p.distance
            for (i in p.end .. D) arr[i] = min(dist + i - p.end, arr[i])
        }
    }
}

[코드]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.PriorityQueue
import kotlin.math.min

data class highway(val start : Int, val end : Int, val distance : Int) : Comparable<highway> {
    override fun compareTo(other: highway): Int {
        return start - other.start
    }
}
fun main()
{
    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.`out`))

    var tmp = br.readLine().split(" ").map{it.toInt()}
    var N = tmp[0]
    var D = tmp[1]
    var pq = PriorityQueue<highway>()
    var arr = IntArray(D+1){i -> i}
    repeat(N)
    {
        tmp = br.readLine().split(" ").map{it.toInt()}
        pq.add(highway(tmp[0],tmp[1],tmp[2]))
    }
    while (pq.isNotEmpty())
    {
        val p = pq.poll()
        if(p.end <= D) {
            if(p.end - p.start <= p.distance) continue
            if(arr[p.end] > arr[p.start] + p.distance){
                val dist = arr[p.start] + p.distance
                for (i in p.end .. D) arr[i] = min(dist + i - p.end, arr[i])
            }
        }
    }
    bw.write(arr[D].toString())
    bw.flush()
    bw.close()
}