[Swift] BOJ 1516 게임 개발

BOJ 1516 게임 개발

 

오랜만에 위상정렬 문제인데 시간을 계산해야 해서 알고리즘이 약간 복잡했음.

예전에 속에 있어서 풀었는데, 위상정렬 문제를 오랜만에 보니까 알고리즘이 가물가물해서 엄청 오래걸렸음.

 

좋았던 점은 알고리즘을 단기 암기식으로 한게 아니라, 원리를 명확하게 알아두어서 시간만 여유롭다면 직접 천천히 구현해가면서 할 수 있음.

 

 

문제풀이 플로우

 

우선 input은 기존의 위상정렬과 동일하게 Input을 받는다.

 

가장 중요한 건 시간을 처리하는 부분

 

1. 우선 초기에 queue에 들어간 값의 경우에는 시간을 계산할 수 계산할 수 없어서 result에 세팅

2. while문을 위상정렬과 동일한 로직으로 돈다.

 -> while문 내에서 maxTime을 계산해주는데

 2-1. 내 선수(내가 만족해야 하는 조건)의 초기 time값과 갱신된 시간을 비교하여 더 큰 값을 maxTime에 넣어준다.

 2-2.  이 코드를 보자.

 

result[i] = max(result[i], (maxTime + time[i]))

 

왜 이걸 이렇게 작성해야 하냐면 특정 i가 여러번 갱신될 수 있는데, 일전에 계산된 값보다 현재 값이 작은 경우가 존재할 수 있음

 

// 2-2에 대한 반례
5
10 -1
20 1 -1
30 2 -1
40 3 5 -1
100 -1

// 내 알고리즘에 의하면
graph: [1: [2], 5: [4], 2: [3], 3: [4]]

 

graph를 보면 4의 경우에는 5와 3에서 두번 갱신되는데, 더 큰 값을 들고 있어야 해서 2-2 작업이 필요하다.

 

 

 

샘플 코드

        import Foundation
        // input은 건물의 개수
        let input = Int(readLine()!)!
        
        var graph = [Int: [Int]]() // 선수 건물에 대한 정보
        var indegree = [Int](repeating: 0, count: input+1) // 진입차수 정보
        indegree[0] = -1 // 건물번호 1번부터라 index바로 사용하려고
        
        var time = [Int](repeating: 0, count: input+1)
        time[0] = 0 // 건물번호 1번부터라서 인덱스를 그냥 바로 사용하기 위함
        
        for i in 1...input {
            let info = readLine()!.split(separator: " ").map { Int(String($0))! }
            time[i] = info[0]
            
            info[1..<info.count-1].forEach {
                if $0 != -1 {
                    if graph[$0] == nil {
                        graph[$0] = [i]
                    } else {
                        graph[$0]!.append(i)
                    }
                    
                    indegree[i] += 1
                }
            }
            
        }
        
//        print(graph)
//        print(indegree)
//        print("time \(time)")
        
        var queue = [Int]()
        indegree.enumerated().forEach {
            if $0.element == 0 {
                queue.append($0.offset)
            }
        }
        
//        print(queue)
        
        var result = [Int](repeating: 0, count: input+1)
        result[0] = 0 // 건물번호 1번부터라서 인덱스를 그냥 바로 사용하기 위함
        
        // 큐가 빌때까지
        queue.forEach { index in
            result[index] = time[index]
        }
        while !queue.isEmpty {
//            print("queue \(queue)")
            let now = queue.removeFirst()
            // 내 선수들의 합의 최솟값을 찾는다.
            
            
            
            // 해당원소와 연결된 노드들의 진입차수에서 -1
            if let sequence = graph[now] {
                let maxTime = max(time[now], result[now])
                
                for i in sequence {
                    indegree[i] -= 1
                    
                    if indegree[i] == 0 {
                        queue.append(i)
                    }
                    result[i] = max(result[i], (maxTime + time[i]))
                }
                
            }
            
        }
        
//        print(result)
        for item in result[1...] {
            print(item)
        }