백준 1005 ACM Craft

출처: www.acmicpc.net/problem/1005

분류: 위상정렬

---

접근방식

특정 순서가 있는 방향성 비순환 그래프(DAG)로 위상정렬의 개념으로 해결할 수 있는 문제였습니다.

위상정렬 개념 다시보기

 

다음 건물을 짓기 위해서는 그 전의 건물이 모두 다 지어져야 하므로 해당 건물을 짓기 위해 필요한 시간을 체크하는 배열을 하나 두고

연결을 끊으면서 가장 오래 걸리는 시간으로 업데이트를 해줍니다.

for adj in adjacent[run] {
    adjCount[adj] -= 1
    if totalTime[adj] < totalTime[run] + runTime[adj] {
        totalTime[adj] = totalTime[run] + runTime[adj]
    }
    if adjCount[adj] == 0 {
        runQueue.enqueue(adj)
    }
}

 

그리고 입력이 많기 때문에 swift로는 그냥 readLine으로 입력을 받으면 시간초과가 납니다.. ㅠㅠ

FileIO로 빠른 입력을 받아야만 통과할 수 있었습니다!

 

해결방법

import Foundation

struct DoubleStackQueue<Element> {
    private var inbox: [Element] = []
    private var outbox: [Element] = []
    
    var isEmpty: Bool{
        return inbox.isEmpty && outbox.isEmpty
    }
    
    var count: Int{
        return inbox.count + outbox.count
    }
    
    var front: Element? {
        return outbox.last ?? inbox.first
    }
    
    init() { }
    
    init(_ array: [Element]) {
        self.init()
        self.inbox = array
    }
    
    mutating func enqueue(_ n: Element) {
        inbox.append(n)
    }
    
    mutating func dequeue() -> Element {
        if outbox.isEmpty {
            outbox = inbox.reversed()
            inbox.removeAll()
        }
        return outbox.removeLast()
    }
}

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
    }
}

// example
let fIO = FileIO()
let n = fIO.readInt()
let command = [fIO.readInt(), fIO.readInt(), fIO.readInt()]

// t
for _ in 0..<fIO.readInt() {
    let (n, k) = (fIO.readInt(), fIO.readInt())
    
    var runTime = [0]
    for _ in 0..<n {
        runTime.append(fIO.readInt())
    }
    
    var adjacent = [[Int]](repeating: [Int](), count: n+1)
    var adjCount = [Int](repeating: 0, count: n+1)
    adjCount[0] = 1 // 0번은 사용하지 않음
    var totalTime = runTime
    var runSet = Set<Int>(1...n)
    for _ in 0..<k {
        let (s, e) = (fIO.readInt(), fIO.readInt())
        adjacent[s].append(e)
        adjCount[e] += 1
        runSet.remove(e)
    }
    
    let w = fIO.readInt()
    
    var runQueue = DoubleStackQueue(Array(runSet))
    
    while !runQueue.isEmpty {
        let run = runQueue.dequeue()
        guard run != w else { break }
        for adj in adjacent[run] {
            adjCount[adj] -= 1
            if totalTime[adj] < totalTime[run] + runTime[adj] {
                totalTime[adj] = totalTime[run] + runTime[adj]
            }
            if adjCount[adj] == 0 {
                runQueue.enqueue(adj)
            }
        }
    }
    
    print(totalTime[w])
}

 

 

배운점

처음에 다음 건물을 짓기 전 해당 턴을 별도로 담아뒀다가 전체 큐에 옮겨 담는 식으로 했었는데, 

그냥 최대 시간으로 업데이트 해주는 방식으로 간단하게 해결할 수 있었다.