[백준 1005] ACM Craft

백준 1005번: ACM Craft - 상세 풀이

🔍 1. 문제 소개

ACM Craft는 건물 건설 순서가 정해져 있지 않고, 각 건물의 건설에는 특정 시간이 소요되는 게임입니다. 각 건물은 특정 선행 건물의 건설이 완료된 후에만 건설을 시작할 수 있으며, 여러 건물이 동시에 건설될 수도 있습니다. 특정 건물 W를 건설하는 데 필요한 최소 시간을 구하는 것이 목표입니다.

💡 2. 문제 해석

문제의 핵심은 위상 정렬(Topological Sort)을 활용하여 건설 순서를 정한 후, 다이나믹 프로그래밍을 적용하여 최소 건설 시간을 계산하는 것입니다. 건물과 건설 순서 규칙을 유향 비순환 그래프(DAG)로 모델링하여 해결할 수 있습니다.

🧠 3. 접근 방법

문제 해결을 위한 가장 효율적인 방법은 위상 정렬을 이용하는 것입니다. 위상 정렬을 통해 건물 건설 순서를 정한 후, 각 건물의 건설 시간을 고려하여 최소 시간을 계산합니다. 각 건물의 건설을 시작할 수 있는 시점은 그 건물에 대한 모든 선행 건물의 건설이 완료된 시점입니다. 따라서, 각 건물의 건설 완료 시간은 그 건물의 건설 시간과 그 건물에 대한 모든 선행 건물의 건설 완료 시간 중 최댓값의 합으로 계산할 수 있습니다.

⚙️ 4. 구현 과정

1. 입력 받기: 건물의 개수 N, 건설 순서 규칙의 개수 K, 각 건물의 건설 시간 D, 건설 순서 규칙(X, Y), 목표 건물 W를 입력받습니다.
2. 그래프 생성: 건물을 노드로, 건설 순서 규칙을 간선으로 하는 유향 그래프를 생성합니다. 각 노드에 진입 차수(indegree)를 저장합니다.
3. 위상 정렬 수행: 진입 차수가 0인 노드들을 큐에 넣고, 큐가 빌 때까지 다음을 반복합니다:
   • 큐에서 노드 u를 꺼내 해당 건물의 건설 완료 시간을 갱신합니다.
   • u에서 나가는 간선의 목표 노드 v의 진입 차수를 감소시키고, v의 건설 완료 시간을 업데이트합니다.
   • 진입 차수가 0이 되면 v를 큐에 추가합니다.
4. 최소 시간 출력: 목표 건물 W의 건설 완료 시간을 출력합니다.

💻 5. 코드 설명

import java.util.*

fun main() {
    val t = readLine()!!.toInt()
    repeat(t) {
        val (n, k) = readLine()!!.split(" ").map { it.toInt() }
        val d = readLine()!!.split(" ").map { it.toInt() }.toIntArray()
        val graph = Array(n + 1) { mutableListOf() }
        val indegree = IntArray(n + 1)
        repeat(k) {
            val (x, y) = readLine()!!.split(" ").map { it.toInt() }
            graph[x].add(y)
            indegree[y]++
        }
        val w = readLine()!!.toInt()

        val queue: Queue = LinkedList()
        val time = IntArray(n + 1)
        for (i in 1..n) {
            if (indegree[i] == 0) {
                queue.offer(i)
                time[i] = d[i - 1]
            }
        }

        while (queue.isNotEmpty()) {
            val u = queue.poll()
            for (v in graph[u]) {
                time[v] = maxOf(time[v], time[u] + d[v - 1])
                indegree[v]--
                if (indegree[v] == 0) {
                    queue.offer(v)
                }
            }
        }
        println(time[w])
    }
}

⏱️ 6. 시간 복잡도와 공간 복잡도 분석

• 시간 복잡도: O(V + E), V는 노드(건물)의 개수, E는 간선(건설 순서 규칙)의 개수입니다. 위상 정렬과 각 노드의 건설 완료 시간 계산이 포함됩니다.
• 공간 복잡도: O(V + E), 그래프와 시간 계산을 위한 배열이 필요합니다.

🎯 7. 결론

이 문제는 위상 정렬 알고리즘을 활용하여 효율적으로 해결할 수 있습니다. Queue와 IntArray를 사용하여 코드의 효율성을 높였습니다. 다른 알고리즘(예: 다익스트라 알고리즘)을 사용할 수도 있지만, 위상 정렬이 이 문제에 더 적합하고 효율적입니다.