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