Swift) 백준 1005번 ACM Craft - G3

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

1005번: ACM Craft

문제 풀이: 위상정렬을 이용하여 풀이했다. 유의해야할 점은 노드를 큐에 추가하지 않더라도, 시간을 갱신 해야만 한다는 점이다. 

import Foundation

final class FileIO {
    private var buffer:[UInt8]
    private var index: Int
    
    init(fileHandle: FileHandle = FileHandle.standardInput) {
        buffer = Array(fileHandle.readDataToEndOfFile())+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
        index = 0
    }
    
    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }
        
        return buffer.withUnsafeBufferPointer { $0[index] }
    }
    
    @inline(__always) func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true
        
        while now == 10
                || now == 32 { now = read() } // 공백과 줄바꿈 무시
        if now == 45{ isPositive.toggle(); now = read() } // 음수 처리
        while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }
        
        return sum * (isPositive ? 1:-1)
    }
    
    @inline(__always) func readString() -> String {
        var str = ""
        var now = read()
        
        while now == 10
                || now == 32 { now = read() } // 공백과 줄바꿈 무시
        
        while now != 10
                && now != 32 && now != 0 {
            str += String(bytes: [now], encoding: .ascii)!
            now = read()
        }
        
        return str
    }
}

let fileIO = FileIO()
let t = fileIO.readInt()

struct Node {
    let num: Int
    let completeTime: Int
}

for _ in 0..<t {
    let n = fileIO.readInt()
    let k = fileIO.readInt()
    var buildingValues = [0]
    for _ in 0..<n {
        buildingValues.append(fileIO.readInt())
    }
    var inDegree: [Int] = Array(repeating: 0, count: n+1)
    var courseArr: [[Int]] = Array(repeating: Array(repeating: 0, count: 0), count: n+1)
    var timeArr: [Int] = Array(repeating: 0, count: n+1)
    for _ in 0..<k {
        let start = fileIO.readInt()
        let end = fileIO.readInt()
        courseArr[start].append(end)
        inDegree[end] += 1
    }
    let destination = fileIO.readInt()
    func topology() {
        var queue: [Node] = []
        var result: [Int] = []
        for i in 1...n {
            if inDegree[i] == 0 {
                queue.append(.init(num: i, completeTime: buildingValues[i]))
            }
        }
        while inDegree[destination] > 0 {
            let visitNode = queue.removeFirst()
            result.append(visitNode.num)
            for j in 0..<courseArr[visitNode.num].count {
                let nextNode = courseArr[visitNode.num][j]
                inDegree[nextNode] -= 1
                timeArr[nextNode] = max(timeArr[nextNode], timeArr[visitNode.num]+buildingValues[visitNode.num])
                if inDegree[nextNode] == 0 {
                    queue.append(.init(num: nextNode, completeTime: timeArr[nextNode]))
                }
            }
        }
        print(timeArr[destination]+buildingValues[destination])
    }
    
    topology()
}