[Algorithm] 백준 - 1005번 ACM Craft (Swift)

문제 소개

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

나에게 Swift 로 알고리즘을 푸는 것에 대한 깊은 고통...을 안겨준 문제이다... 이유는 문제 푸는 방법은 맞았지만... Swift 에서 입력량이 많은 경우 시간초과가 빈번하게 발생하기 때문에 최대한 방법을 찾았으나 결국 파일입력 코드를 사용해버렸다...!
 

문제 풀이

파일 입출력

라이노님의 클래스를 사용했다. (감사합니다)

ps할 때 입력을 한꺼번에 받기 위한 유틸리티 클래스. fread의 swift 버전.

final class FileIO {
    private let buffer:[UInt8]
    private var index: Int = 0

    init(fileHandle: FileHandle = FileHandle.standardInput) {
        
        buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
    }

    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }

        return buffer[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 now = read()

        while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시

        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
    }

    @inline(__always) func readByteSequenceWithoutSpaceAndLineFeed() -> [UInt8] {
        var now = read()

        while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시

        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return Array(buffer[beginIndex..<(index-1)])
    }
}

// 사용 방법

let fileIO = FileIO()
let n = fileIO.readInt()
print(n) // control + D 눌러야 출력 됨

 
이제 이 클래스를 활용하여 입출력을 받으면 된다!
 

DP 를 사용한 풀이 (시간초과)

let fileIO = FileIO()

let t = fileIO.readInt()

for _ in 0..<t {
    let n = fileIO.readInt()
    let k = fileIO.readInt()
    var ds = [Int]()
    
    for _ in 0..<n {
        let d = fileIO.readInt()
        ds.append(d)
    }
    
    var needs = Array(repeating: [Int](), count: n+1)
    
    for _ in 0..<k {
        let x = fileIO.readInt()
        let y = fileIO.readInt()
        needs[y].append(x)
    }
    
    let w = fileIO.readInt()
    
    var dp = Array(repeating: 0, count: n+1)
    
    func findCost(_ n: Int) -> Int {
        if dp[n] == 0 {
            var cost = 0
            
            for b in needs[n] {
                cost = max(cost, findCost(b))
            }
            
            cost += ds[n - 1]
            dp[n] = cost
        }
        
        return dp[n]
    }
    
    print(findCost(w))
}

BFS + 위상정렬 사용

count 배열을 두어 노드의 선행관계를 판별하였다.

let fileIO = FileIO()

let t = fileIO.readInt()

for _ in 0..<t {
    let n = fileIO.readInt()
    let k = fileIO.readInt()
    
    var ds = [Int]()
    for _ in 0..<n {
        ds.append(fileIO.readInt())
    }
    
    var graph = Array(repeating: [Int](), count: n + 1)
    var count = Array(repeating: 0, count: n + 1)
    
    for _ in 0..<k {
        let x = fileIO.readInt()
        let y = fileIO.readInt()
        graph[x].append(y)
        count[y] += 1
    }
    
    let w = fileIO.readInt()
    
    var dp = Array(repeating: 0, count: n + 1)
    var queue = [Int]()
    
    for i in 1...n {
        if count[i] == 0 {
            queue.append(i)
            dp[i] = ds[i - 1]
        }
    }
    
    var idx = 0
    while idx < queue.count {
        let current = queue[idx]
        idx += 1
        
        for next in graph[current] {
            dp[next] = max(dp[next], dp[current] + ds[next - 1])
            count[next] -= 1
            if count[next] == 0 {
                queue.append(next)
            }
        }
    }
    
    print(dp[w])
}

결과