백준 1005 코틀린

위상정렬이라는 개념을 몰라 시간 초과로 실패한 문제다.

위상정렬은 단반향에(개수는 상관x) 순서가 정해진 문제에 사용된다.

보통 선행 정점을 가지지 않는 정점들을 q에 넣어 해당 정점이 가르키는 정점들을 순서로 진행 하는 알고리즘이다.

 

fun main() {
    val t = readLine()!!.toInt()

    for (i in 0 until t) {
        val input = readLine()!!.split(" ")
        val n = input[0].toInt()
        val rules = Array(n + 1) { ArrayList<Int>() }
        val priceInput = readLine()!!.split(" ").map {
            it.toInt()
        }
        val degree = Array(n + 1) { 0 }

        for (j in 0 until input[1].toInt()) {
            val rule = readLine()!!.split(" ")
            rules[rule[0].toInt()].add(rule[1].toInt())
            degree[rule[1].toInt()]++
        }

        val end = readLine()!!.toInt()
        sort(rules, priceInput, degree, end)
    }

}

fun sort(
    rules: Array<ArrayList<Int>>,
    priceInput: List<Int>,
    degree: Array<Int>,
    end: Int
) {
    val q: Queue<Int> = LinkedList()
    val results  = priceInput.toIntArray()

    for (i in 1 until degree.size) {
        if (degree[i] == 0) {
            q.add(i)
        }
    }
    while (!q.isEmpty()) {
        val num = q.remove()

        for(i in rules[num]) {
            degree[i]--
            if (degree[i]==0) {
                q.add(i)
            }
            results[i-1] = max(results[i-1], results[num-1]+priceInput[i-1])
        }
    }
    println(results[end-1])
}