백준 - 게임 개발 (1516)

let N = Int(readLine()!)!
var graph: [[Int]] = Array(repeating: [], count: N+1)
var indegree = Array(repeating: 0, count: N+1) // 진입차수
var selfBuild = Array(repeating: 0, count: N+1) // 각 건물 짓는데 걸리는 시간
var result = [Int]()
var stack = [Int]()

// 인접리스트 및 진입 차수, 각 건물 짓는 시간 업데이트
for i in 0..<N {
    let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
    selfBuild[i+1] = input[0]
    for j in 1..<input.count {
        if input[j] == -1 { break }
        graph[input[j]].append(i+1)
        indegree[i+1] += 1
    }
}

result = selfBuild

// 위상정렬
for i in 1...N {
    if indegree[i] == 0 {
        stack.append(i)
    }
}

while !stack.isEmpty {
    let now = stack.removeLast()
    for next in graph[now] {
        indegree[next] -= 1
        result[next] = max(result[next], result[now] + selfBuild[next])
        if indegree[next] == 0 {
            stack.append(next)
        }
    }
}

for i in 1...N {
    print(result[i])
}

어떤 건물을 짓기 위해 먼저 지어야 하는 건물이 있을 수 있다 → 위상정렬 알고리즘을 사용할 수 있다

1. result 배열 (각 건물 짓는 데 필요한 최소 시간 저장하는 배열) 내 각 값을 건물을 짓는 데 걸리는 시간으로 초기화 한다.
2. 위상 정렬을 실행하면서 result 배열의 값을 max(현재 result 배열의 값, 이전 건물에 저장된 최대 시간 + 현재 건물을 짓는 데 걸리는 시간) 로 설정한다.
3. result 배열 내 값들을 출력한다.