1. 문제 정의
임계 경로 문제는 그래프 이론에서 중요한 문제로, 주어진 작업의 완료에 필요한 최소 시간을 계산하는 문제입니다. 각 작업이 다른 작업에 의존하는 구조로, 작업의 실행 순서를 결정해야 합니다. 이 문제를 통해 우리는 작업 간의 의존성을 고려한 최적의 일정을 생성해야 합니다.
2. 문제 설명
주어진 작업 목록과 각 작업의 실행 시간을 기반으로 해서, 모든 작업을 완료하는 데 필요한 최소 시간을 계산하시오. 작업은 다음과 같은 형식으로 주어집니다:
tasks = [
(1, 3, [2]), // 작업 1은 작업 2가 완료된 후에 시작 가능
(2, 2, []), // 작업 2는 독립적으로 진행 가능
(3, 4, [1, 2]) // 작업 3은 작업 1과 2가 완료된 후에 시작 가능
]
문제 입력 형식
각 작업은 튜플로 구성되며, 튜플의 첫 번째 요소는 작업 ID, 두 번째 요소는 작업 수행 시간, 세 번째 요소는 의존하는 작업 ID 리스트입니다.
문제 출력 형식
모든 작업을 완료하는 데 필요한 최소 시간을 정수로 출력하시오.
3. 문제 해결 과정
이 문제를 해결하기 위해 다음과 같은 절차를 따르겠습니다.
- 의존성 그래프 생성: 각 작업 간의 의존성을 그래프 형태로 표현합니다.
- 최장 경로 찾기: 각 작업의 시작 시간을 계산하기 위해 깊이 우선 탐색(DFS)을 사용하여 최장 경로를 찾습니다.
- 최종 시간 계산: 전체 작업을 완료하는 데 필요한 시간을 계산합니다.
3-1. 의존성 그래프 생성
우선 입력된 작업을 그래프 구조로 변환합니다. 각 작업은 노드로 표현되며, 의존 관계는 엣지로 나타냅니다.
3-2. 최장 경로 찾기
깊이 우선 탐색을 통해 각 작업을 시작할 수 있는 시점을 결정합니다. 의존 작업이 끝나는 시간을 고려하여 작업의 시작 시간을 기록합니다. 그 후, 모든 작업을 방문하여 최장 경로를 찾아 나가야 합니다.
3-3. 최종 시간 계산
모든 작업을 완료하는 데 필요한 시간을 기반으로 최종 작업의 종료 시간을 판단하여 최소 시간을 계산합니다.
4. 스위프트 코드 구현
아래는 위의 알고리즘을 기반으로 한 스위프트 코드입니다.
import Foundation
struct Task {
let id: Int
let time: Int
let dependencies: [Int]
}
func minimumCompletionTime(tasks: [Task]) -> Int {
var graph = [Int: [Int]]() // 의존성 그래프
var inDegree = [Int: Int]() // 진입 차수
var completionTime = [Int: Int]() // 완료 시간 저장
// 그래프와 진입차수 초기화
for task in tasks {
graph[task.id] = []
inDegree[task.id] = task.dependencies.count
completionTime[task.id] = 0
}
// 그래프 생성
for task in tasks {
for dependency in task.dependencies {
graph[dependency]?.append(task.id)
}
}
var queue = [Int]() // 시작할 수 있는 작업들
for task in tasks {
if inDegree[task.id] == 0 {
queue.append(task.id)
completionTime[task.id] = task.time // 독립적인 작업 시간을 초기화
}
}
var maxCompletionTime = 0
// 위상 정렬에 사용하는 큐
while !queue.isEmpty {
let currentTaskId = queue.removeFirst()
let currentTaskTime = completionTime[currentTaskId]!
// 현재 작업의 자식 작업 방문
for dependentTaskId in graph[currentTaskId]! {
completionTime[dependentTaskId] = max(completionTime[dependentTaskId]!, currentTaskTime + tasks.first { $0.id == dependentTaskId }!.time)
// 진입 차수 감소
inDegree[dependentTaskId]! -= 1
// 진입 차수가 0이 되면 큐에 추가
if inDegree[dependentTaskId] == 0 {
queue.append(dependentTaskId)
}
}
maxCompletionTime = max(maxCompletionTime, currentTaskTime)
}
return maxCompletionTime
}
// 테스트 케이스
let tasks = [
Task(id: 1, time: 3, dependencies: [2]),
Task(id: 2, time: 2, dependencies: []),
Task(id: 3, time: 4, dependencies: [1, 2])
]
let result = minimumCompletionTime(tasks: tasks)
print("모든 작업을 완료하는 데 필요한 최소 시간: \(result) 초")
5. 코드 설명
위 코드에서는 임계 경로 문제를 해결하기 위해 그래프를 구성하고, 깊이 우선 탐색을 통해 각 작업의 완료 시간을 계산하였습니다. 각 작업에 대한 의존성을 확인하고 완료 시간을 업데이트하며, 최종적으로 모든 작업을 완료하는 데 걸리는 최소 시간을 출력합니다.
6. 결론
임계 경로 구하기 문제는 작업 간의 의존성을 관리하는 중요한 알고리즘 문제입니다. 이 문제를 풀면서 그래프 이론에 대한 이해를 높일 수 있으며, 코딩 테스트에서 자주 출제되는 유형이기도 합니다. 위에서 설명한 방법을 바탕으로 다양한 형태의 문제를 연습해봅시다!