코틀린 코딩테스트 강좌, 임계 경로 구하기

문제 정의

주어진 연결된 그래프에서 시작 노드부터 도착 노드까지의 임계 경로를 구하는 문제입니다. 임계 경로란 그래프에서 요구되는 작업을 수행하는 데 필요한 최소 시간 또는 거리를 나타내며, 프로젝트 관리 및 자원의 최적 배분에 중요한 역할을 합니다.

예를 들어, 각 작업이 완료되는 데 걸리는 시간을 나타내는 다이아그램이 주어졌다고 가정합니다. 각 작업이 완료되기 위해서는 다른 작업들이 먼저 완료되어야 하는 조건이 있을 수 있습니다. 이러한 조건을 반영한 Directed Acyclic Graph (DAG)를 활용하여 문제를 해결할 수 있습니다.

입력 형식

• 첫 번째 줄에 자연수 N (작업의 수)이 주어진다.
• 다음 N개의 줄에는 작업의 번호, 소요 시간, 의존 작업의 번호가 공백으로 구분되어 주어진다. 의존 작업은 없으면 -1로 표시된다.

출력 형식

임계 경로의 길이 (총 소요 시간)를 출력한다.

예시

입력

            5
            1 3 -1
            2 2 1
            3 1 1
            4 4 2
            5 2 3
            

출력

            9
            

문제 풀이 과정

이 문제를 해결하기 위해서는 다음과 같은 과정을 따릅니다:

1. 그래프 모델링: 각 작업을 노드로, 의존 관계를 간선으로 표현하여 Directed Acyclic Graph (DAG)를 생성합니다.
2. 위상 정렬: 간선을 따라 작업을 수행하기 위해서는 작업의 의존성을 고려해야 합니다. 이를 위해 위상 정렬을 수행하여 노드를 정렬합니다.
3. 최장 경로 계산: 위상 정렬 결과를 따라 각 작업의 소요 시간을 누적하여 최장 경로를 계산합니다. 노드가 가지는 소요 시간의 최대값을 저장하여 최종 결과를 도출합니다.

코틀린 코드 구현

            fun main() {
                val n = readLine()!!.toInt()
                val time = IntArray(n + 1)
                val graph = Array(n + 1) { mutableListOf() }
                val indegree = IntArray(n + 1)
                
                for (i in 1..n) {
                    val input = readLine()!!.split(" ").map { it.toInt() }
                    time[i] = input[1]
                    if (input[2] != -1) {
                        graph[input[2]].add(i)
                        indegree[i]++
                    }
                }

                val dp = IntArray(n + 1)
                val queue: Queue = LinkedList()

                for (i in 1..n) {
                    if (indegree[i] == 0) {
                        queue.offer(i)
                        dp[i] = time[i]
                    }
                }

                while (queue.isNotEmpty()) {
                    val current = queue.poll()
                    for (next in graph[current]) {
                        dp[next] = maxOf(dp[next], dp[current] + time[next])
                        indegree[next]--
                        if (indegree[next] == 0) {
                            queue.offer(next)
                        }
                    }
                }

                println(dp.maxOrNull())
            }
            

코드 설명

위 코드는 아래와 같은 단계로 구성되어 있습니다:

1. 작업의 수 N을 입력받습니다.
2. 작업의 실행 시간을 저장하는 time 배열과 그래프 간선을 저장하는 graph 배열을 초기화합니다.
3. 각 작업의 의존 관계를 읽어들여 그래프와 진입 차수를 설정합니다.
4. Queue를 사용하여 위상 정렬을 수행하며 최장 경로를 계산합니다. 각 작업의 소요 시간을 dp 배열에 누적합니다.
5. 최장 경로의 결과를 출력합니다.

문제 해결 전략

임계 경로 구하기 문제는 프로젝트 관리에서 시간 관리를 위한 중요한 요소입니다. 따라서 이러한 문제를 해결하기 위해서는:

• 코드 최적화: 성능을 고려하여 알고리즘을 최적화하는 것이 중요합니다.
• 분석 및 계획: 문제 요구 사항을 체계적으로 분석하고 해결 방안을 계획하는 것이 필수적입니다.
• 유사 문제 연습: 유사한 문제를 통해 경험을 쌓고 다양한 상황을 고려하는 연습이 필요합니다.