[백준/BOJ] 1005번: ACM Craft

문제

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

1005번: ACM Craft

해설

선행 순서가 정해져 있고, 이를 특정 건물을 짓기까지 얼마나 오랜 시간이 걸릴지 구해야 한다.

선행 순서가 있는 문제에서 전체적인 순서를 구할 때 위상 정렬을 사용한다.

문제의 예제 2번을 보며 풀이를 해보자.

우선 차수가 0인 1번 정점부터 시작을 한다.

위상 정렬을 진행하므로 1번 정점을 큐에 넣고, 이와 연결된 간선들을 모두 제거한다.

이제 차수가 0인 것은 2번과 3번이다.

우리는 7번 건물을 짓는 것이 목표이므로 2번과 3번 건물을 모두 지어야만 한다.

이 중 더 오래 걸리는 시간을 더해주면 된다.

위 표에서 소요 시간을 result 배열로 선언했는데, result[다음 건물]  = max(result[다음 건물], result[현재 건물] + runningtime(시간)[다음 건물])을 비교해준다.

즉, result[2] = max(20, 20 + 10)이므로 result[2] = 30이 된다.

또한 result[3] = max(10, 10 +1)로 result[3] = 11이다.

 

이 과정을 계속 반복해보자.

이제 2와 3이 큐에 들어가고 이와 연결된 간선들을 모두 제거한다.

중간 과정이 많이 생략되었지만 설명을 해보자면,

우선 2와 3이 큐에 있고, 2가 먼저 pop이 된다.

이때, 2와 연결되있던 간선은 4와 5가 있고, 즉 result[4] = max(5, 30 + 5), result[5] = max(8, 30 + 8)이 된다.

또한 3과 연결되있던 6은 result[6] = max(11, 11 + 7)이 된다.

7은 5, 6과 모두 연결되있었다.

따라서 result[7] = max(35, 35 + 1)을 한 후, result[7] = max(36, 38 + 1)이 된다.

따라서 result[7] = 39이다.

 

우리는 7번 건물을 가장 빨리 짓는 시간을 알아내면 된다. 따라서 수행을 끝내고, result[7]을 출력해주면 된다.

코드

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

private lateinit var graph: ArrayList<ArrayList<Int>>
private lateinit var degree: IntArray
private lateinit var runningTime: IntArray

fun main() = with(System.`in`.bufferedReader()) {
    val testCase = readLine().toInt()
    repeat(testCase) {
        val (buildingCnt, ruleCnt) = readLine().split(" ").map { it.toInt() }

        graph = ArrayList(ArrayList())
        repeat(buildingCnt + 1) { graph.add(ArrayList()) }

        degree = IntArray(buildingCnt + 1)
        runningTime = IntArray(buildingCnt + 1)

        val st = StringTokenizer(readLine())
        for(i in 1 .. buildingCnt) { runningTime[i] = st.nextToken().toInt() }

        repeat(ruleCnt) {
            val (first, second) = readLine().split(" ").map { it.toInt() }
            graph[first].add(second)
            degree[second]++
        }

        val targetBuilding = readLine().toInt()

        build(buildingCnt, targetBuilding)
    }
}

private fun build(n: Int, targetBuilding: Int) {
    val que: Queue<Int> = LinkedList()
    val result = IntArray(n + 1)

    for(i in 1 .. n) {
        result[i] = runningTime[i]

        if(degree[i] == 0) que.add(i)
    }

    while(que.isNotEmpty()) {
        val cur = que.poll()

        for(i in graph[cur]) {
            result[i] = max(result[i], result[cur] + runningTime[i])
            degree[i]--

            if(degree[i] == 0) que.add(i)
        }
    }

    println(result[targetBuilding])
}