[2056번] 작업 / Swift

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

2056번: 작업

 

---

위상정렬을 사용해서 풀었다.

위상정렬 결과 자체를 이용하지는 않고 그 과정에서 각 작업에 대해서 인접한 작업을 확인할 때, 인접한 작업에 적힌 누적값이 현재까지 누적된 값 + 인접한 작업 그자체에 걸리는시간 보다 크다면 인접한 작업에 적힌 누적값을 갱신하는 방법으로 가장 긴 경우를 찾았다.

 

그리고 문제에서 주어진 조건인,

 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재

이 부분을 처리하기 위해서 연결되어 있지 않은 작업들 마지막 노드를 처리할 때마다 stack에 담고, 가장 오래걸린 경우 하나를 반환하게 했다.

import Foundation

let n = Int(readLine()!)!
var graph = [[Int]](repeating: [], count: n+1)
var indegree = [Int](repeating: 0, count: n+1)
var cost = [Int](repeating: 0, count: n+1)
var result = [Int](repeating: 0, count: n+1)

for i in (1...n) {
    let input = readLine()!.split(separator: " ").map {Int(String($0))!}
    cost[i] = input[0]
    result[i] = input[0]
    for j in (2..<2+input[1]) {
        graph[i].append(input[j])
        indegree[input[j]] += 1
    }
}

func topologySort(_ start: Int) -> [Int] {
    var queue = indegree[1...].enumerated().filter { $0.element == 0 }.map {$0.offset + 1}
    var stack = [Int]()
    while !queue.isEmpty {
        let first = queue.removeFirst()
        result.append(first)
        if graph[first].isEmpty {
            stack.append(result[first])
        }
        
        for element in graph[first] {
            result[element] = max(result[element], result[first] + cost[element])
            indegree[element] -= 1
            if indegree[element] == 0 {
                queue.append(element)
            }
        }
    }
    return stack
}

print(topologySort(n).max()!)