[백준 - 1516] 게임 개발

문제링크

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

data class Building(val number: Int, val time: Int, var degree: Int)

fun main() {
    val bufferedReader = System.`in`.bufferedReader()
    val bufferedWriter = System.out.bufferedWriter()

    val n = bufferedReader.readLine().toInt()
    val nodes = mutableListOf(Building(0, 0, 0)) //◀ index starts with 1
    val graph = Array(n + 1) { mutableListOf<Building>() } //◀ index starts with 1

    for (i in 1..n) {
        val buildingNumbers = bufferedReader
            .readLine()
            .split(" ")
            .map { it.toInt() }
        nodes.add(Building(i, buildingNumbers[0], 0))
        for (j in 1 until buildingNumbers.size) {
            if (buildingNumbers[j] != -1) {
                graph[buildingNumbers[j]].add(nodes[i])
                nodes[i].degree++
            }
        }
    }

    val results = Array(n + 1) { 0 } //◀ index starts with 1
    val queue: Queue<Building> = LinkedList()
    for (i in 1..n) {
        if (nodes[i].degree == 0) {
            queue.add(nodes[i])
            results[i] = nodes[i].time
        }
    }

    while (queue.isNotEmpty()) {
        val currentNode = queue.poll()
        for (connectedNode in graph[currentNode.number]) {
            connectedNode.degree--
            results[connectedNode.number] =
                max(results[connectedNode.number], results[currentNode.number] + connectedNode.time)
            if (connectedNode.degree == 0) {
                queue.add(connectedNode)
            }
        }
    }

    for (i in 1..n) {
        bufferedWriter.write("${results[i]}\n")
    }

    bufferedReader.close()
    bufferedWriter.close()
}

• Topology Sort 결과에 따라 건물을 짓는데 가장 오래 걸린 시간을 계산하면 해당 건물을 짓기 위한 최소 시간을 구할 수 있습니다.

주석 없는 코드를 만들기 위해 노력하는 개발자입니다.

혹시라도 의도가 분명하지 않아보이는 (이해가 되지 않는) 코드가 있으시다면 편하게 답변 달아주시면 정말 감사하겠습니다.