백준 2056 작업

출처: https://www.acmicpc.net/problem/2056

분류: 위상정렬

---

접근방식

나보다 먼저 수행되어야 할 작업이 필요한 위상정렬에 관한 문제였습니다 :)

각 작업을 Node로 정의해서
나보다 먼저 수행되어야 할 작업들을 진입차수, inDegree
내가 끝나길 기다리고 있는 작업들을 nextTasks로 가지고 있도록 만들었습니다.
내가 수행하는 데 걸리는 시간을 workingTime
그리고 자신이 끝나는 시간 endTime을 가지고 있도록 했습니다.
(우선 초기값은 workingTime이고 내가 기다리던 작업이 끝날 때마다 업데이트 시킵니다.)

inDegree가 0인 작업들은 바로 시작이 가능하므로 큐에 담아서 실행시키고,
작업이 끝나면 기다리던 노드로 가서 inDegree를 줄이고 nextTasks에서 제거시키면서 endTime을 갱신합니다.

 

해결방법

class Node {
    var nextTasks = [Int]()
    var inDegree = 0
    var workingTime = 0
    var endTime = 0
    
    func finishTask(at time: Int) {
        inDegree -= 1
        endTime = max(endTime, time + workingTime)
    }
}

let n = Int(readLine()!)!
var tasks = (0..<n).map { _ in Node() }
for idx in 0..<n {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    let (workingTime, inDegree ,inDegrees) = (input[0], input[1], [Int](input.dropFirst(2)))
    tasks[idx].workingTime = workingTime
    tasks[idx].endTime = workingTime
    tasks[idx].inDegree = inDegree
    
    inDegrees.forEach {
        tasks[$0-1].nextTasks.append(idx)
    }
}

var inDegreeZero = [Int]()
for idx in 0..<tasks.count {
    guard tasks[idx].inDegree == 0 else { continue }
    inDegreeZero.append(idx)
}

var lastEndTime = 0
while !inDegreeZero.isEmpty {
    let finish = inDegreeZero.removeFirst()
    let endTime = tasks[finish].endTime
    if endTime > lastEndTime {
        lastEndTime = endTime
    }
    tasks[finish].nextTasks.forEach {
        tasks[$0].finishTask(at: endTime)
        if tasks[$0].inDegree == 0 {
            inDegreeZero.append($0)
        }
    }
}

print(lastEndTime)

 

배운점

풀이 과정을 확실히 정리하고 들어가야되는데

그렇지 않으면 자꾸 꼬이고 이상한 데서 시간을 오래 잡아먹는다...

연습연스읍....✍️