[Kotlin]백준 10217 KCM Travel 시간초과를 벗어나기 위한 노력들

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

10217번: KCM Travel

 

시도횟수 보소...

문제 설명

인천에서 LA까지 M원 이하로 사용하면서 도착할 수 있는 가장 짧은 소요시간을 구하는 문제이다.

 

문제 해결과정

처음에 문제를 읽어보고 당연히 다익스트라로 풀어야겠다고 생각하고 봤는데 고려해야 할 요소가 2가지였다.

가장 빠른 길만 고려해야했다면 너무 쉬운 문제이니 골드1이 아니었겠지.

 

그래서 백트래킹 형태로 visited 여부를 체크하면서 코드를 짰다.

중간에 비용이 M이 넘는지, 거쳐온 공항인지 검사한다고 하더라도 최악의 시간복잡도가 매우 컸다.

틀릴걸 알고 제출했고 역시나 바로 시간초과가 났다.

 

다익스트라로 기록해가면서 푸는 방법도 고민해보고 다른 사람의 풀이도 약간 참고한 결과

i 번째 공항에 도착하고 j원의 비용이 들 때의 최소 시간을 기록해 놓은 배열을 사용하면서 Dijkstra를 수행하는 코드를 만들었다.(M원까지만 기록하면 되므로!)

-> 시간초과

 

PriorityQueue에 들어가는 데이터 양을 줄이기 위해 해당 공항번호에서 지금의 비용보다 많이 들어가면서 시간도 더 많이 걸리는 상황에서의 최소 시간을 수정해주었다.

현재 비용 + 1부터 M까지 경우의 최소시간을 현재의 최소시간으로 update 해주는데, 현재의 최소시간보다 더 적은 최소시간을 만나면 그 뒤는 이미 update되어있을것이므로 update를 멈춘다.

-> 시간초과

 

1번 인천공항에서 모든 무게에 대해 최소 시간을 0으로 세팅하고 다익스트라에 들어가도록 수정했다.

(for문 돌면서 update해주는것 보단 fill이 빠를것 같아서. 사실 최대 10001개라 그렇게 엄청 빨라지진 않겠지만.)

-> 시간초과

 

입력 시 split함수 퍼포먼스보다 StringTokenizer 사용이 나은가? 싶어서 바꿔봤다.

-> 시간초과

이 글을 쓰면서 split과 StringTokenizer사용 퍼포먼스 비교하는 글을 몇개 찾아봤다.
StringTokenizer가 Regex등을 지원하지 않는 등의 이유로 더 빠르다고 함

 

edge들 저장할때나 Priority Queue 쓸때 Pair<Int, Pair<Int, Int>> 형태로 저장한 것을 Airport라는 data class로 바꿔서 저장해주었다.

원래 Priority Queue에 Comparator을 넣어서 비교했었는데 Comparable 인터페이스를 상속받아서 오버라이딩해주었다.

비교할 때 time끼리 비교하고 time이 같을때는 무게가 가벼운것에 우선순위를 둬서 priority queue에 들어가는 데이터 양을 줄여주었다.

-> 통과

 

시간 제한이 10초라서 이 전까지는 실행 시간이 10000ms 그 이상이라는 건데 마지막에 바꿔주고나서 보니까 1700ms로 확 줄었다.

차이가 엄청난가보다.

data클래스도 자주 써야겠다.

 

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.min

var N = 0
var M = 0
var K = 0
var flight = arrayOf<ArrayList<Airport>>()
var ans = 10000000
var dp = arrayOf<IntArray>()

fun Dijkstra(){
    var pq = PriorityQueue<Airport>()
    pq.offer(Airport(1, 0, 0))
    dp[1].fill(0)
    while(pq.isNotEmpty()){
        val now = pq.poll()
        if(dp[now.num][now.cost] >= now.time){
            flight[now.num].forEach{
                val next = it.num
                val nCost = now.cost + it.cost
                val nTime = now.time + it.time
                if((nCost <= M) && (dp[next][nCost] > nTime)){
                    dp[next][nCost] = nTime
                    for(i in nCost + 1..M){
                        if(dp[next][i] <= dp[next][nCost]){
                            break
                        }
                        dp[next][i] = nTime
                    }
                    pq.add(Airport(next, nCost, nTime))
                    if(next == N){
                        ans = min(ans, nTime)
                    }
                }
            }
        }
    }


}

data class Airport(val num: Int = 0, val cost: Int = 0, val time: Int = 0): Comparable<Airport>{
    override fun compareTo(other: Airport): Int {
        if(this.time == other.time){
            this.cost - other.cost
        }
        return time - other.time
    }
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){

    val T = readLine().toInt()
    val sb = StringBuilder()
    repeat(T){
        ans = 10000000
        var tok = StringTokenizer(readLine())
        N = tok.nextToken().toInt()
        M = tok.nextToken().toInt()
        K = tok.nextToken().toInt()
        flight = Array(N + 1){ArrayList<Airport>()}
        dp = Array(N + 1){IntArray(M + 1){10000000} }
        for(i in 1..K){
            tok = StringTokenizer(readLine())
            flight[tok.nextToken().toInt()].add(Airport(tok.nextToken().toInt(), tok.nextToken().toInt(), tok.nextToken().toInt()))
        }

        Dijkstra()

        if(ans == 10000000){
            sb.append("Poor KCM\n")
        }else{
            sb.append(ans)
            sb.append('\n')
        }

    }
    print(sb.toString())
}