3665번: 최종 순위

위상 정렬 알고리즘 (Topology Sort)

정의

이 문제를 위상정렬 알고리즘을 활용해서 풀어야 합니다. 위상 정렬 알고리즘은 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정하기 위해 사용하는 알고리즘입니다.

위상 정렬 알고리즘에서 작업의 선행관계는 그래프의 형태로 주어집니다. 두 정점 A와 B가 있을 때 A에서 B로 방향성이 있는 간선이 존재한다면 A 작업이 B보다 선행해야 한다는 의미입니다.

구현 방법

위상 정렬 알고리즘을 위해서는 주어진 그래프 (= 작업의 순서)를 바탕으로 degree의 갯수를 구해야 합니다. degree는 그래프 이론에서 정점에 연결된 간선의 갯수를 의미하는데요. 위상 정렬 알고리즘은 degree 중에 indegree, 즉 해당 정점으로 들어오는 간선의 갯수를 세어주어야 합니다. (참고로 outdegree는 해당 정점에서 나가는 간선을 의미합니다. 무방향 그래프의 경우 그냥 degree라고 부릅니다.)

이렇게 indegree의 갯수를 세고 나면 indegree의 갯수가 0인 정점을 찾아줍니다. 이 정점은 선행 작업이 없는 작업을 의미합니다. 사전에 수행해야 할 선행 작업이 없으므로 해당 작업을 가장 먼저 실시할 수 있게 됩니다. 해당 정점을 queue에 넣어줍니다.

그리고 나서 queue에서 그 정점을 pop한 이후에 해당 정점에서 다른 정점과 연결된 간선을 전부 지워줍니다. 즉 해당 작업을 수행했으므로 그 작업을 선행작업으로 가지고 있는 작업들을 수행할 수 있는 상태로 바꾸어주는 것입니다. 이렇게 간선을 지워주고 나서 다시 indegree의 갯수가 0인 정점을 찾아서 queue에 넣어주고 pop해서 연결된 간선을 지우는 작업을 반복하면 됩니다.

이렇게 정점의 갯수 만큼 queue에 넣고 빼는 것을 반복하면 최종적으로 작업의 순서를 구할 수 있습니다.

예외적인 Case

위상 정렬을 할 수 없는 경우: Cycle이 있는 그래프

Cycle이 존재하는 그래프의 경우 위상 정렬을 할 수 없습니다. Cycle이 존재한다는 것은 한 정점에서 간선을 타고 이동했을 때 다시 그 정점으로 돌아오는 case가 있다는 의미입니다.

작업의 선행 관계의 관점에서 보면 Cycle은 A라는 작업을 수행하기 위해서 A라는 작업을 먼저 해야 한다는 의미입니다. 즉 모순에 빠지게 되는 것이죠. 따라서 Cycle이 존재하는 그래프는 위상 정렬 알고리즘을 실시할 수 없습니다.

위상 정렬의 결과가 여러가지인 경우

위상 정렬의 결과가 2개 이상인 경우도 존재할 수 있습니다. 예를 들어서 어떤 정점에 연결된 간선을 지웠을 때 indegree가 0이 되는 정점이 동시에 2개 이상 존재할 수도 있습니다. 이런 경우 queue에 어떤 정점을 먼저 넣어도 관계가 없으므로 위상 정렬의 결과는 2개 이상이 되게 됩니다.

시간 복잡도

정점의 갯수가 V, 간선의 갯수가 E일 때 시간 복잡도는 O(V+E)입니다.

문제 풀이 아이디어

위상 정렬 알고리즘

작년의 순위와 작년의 순위와 바뀐 팀이 주어진다는 것은 팀 간의 우선 순위의 관계가 주어진 것입니다. 따라서 해당 정보를 바탕으로 방향 그래프를 만들 수 있는 것이고 그 그래프를 바탕으로 올해의 순위를 위상 정렬을 통해 구해야 하는 것이죠. 문제는 전형적인 위상 정렬 알고리즘 문제의 형태를 가지고 있다고 볼 수 있습니다.

🚫 주의할 점

이 문제에서 주의할 점은 2가지 예외 처리가 있다는 점입니다. 첫 번째는 확실한 순위를 가지고 있지 않는 경우 “?”를 출력하는 것입니다. 이 경우는 위에 설명한 예외적인 Case에서 위상 정렬의 결과가 여러가지인 경우입니다. 이 예외처리를 위해서 indegree가 0이 되는 정점이 2개일 때, 즉 queue 안에 들어있는 정점이 2개인 경우 “?”를 출력하면 됩니다.

두 번째 예외는 데이터에 일관성이 없는 경우입니다. (= 데이터에 모순이 있는 경우) 이 경우는 Cycle이 발생한 경우라고 볼 수 있습니다. Cycle이 존재하는 경우 위상 정렬 알고리즘을 도중에 queue가 비게 됩니다. 예를 들어 A와 B가 서로를 향하는 간선이 존재해서 사이클이 발생한다고 가정을 해봅시다. 그렇다면 A와 B에 연결된 간선은 영원히 지워지지 않게 됩니다. A와 B가 서로의 선행 작업이 되어 서로 queue에 들어가지 못하게 막고 있기 때문입니다.

코드

// 큐 구현
struct Queue {
    private var index: Int = 0
    private var queue = [Int]()
    
    var isEmpty: Bool {
        queue.count == index
    }
    
    var count: Int {
        queue.count - index
    }
    
    mutating func push(_ n: Int) {
        queue.append(n)
    }
    
    mutating func pop() -> Int {
        defer {
            index += 1
        }
        return queue[index]
    }
}

// 테스트 케이스 갯수 입력 받기
let T = Int(readLine()!)!

for _ in 0..<T {
    // 팀 갯수 입력받기
    let n = Int(readLine()!)!
    
    // 자신에게 들어오는 간선 갯수 저장하는 배열 (= 나를 이긴 팀)
    var indegree = Array(repeating: 0, count: n + 1)
    // 승패 정보를 저장하는 이차원 배열 (= 간선 행렬)
    var matrix = Array(repeating: Array(repeating: false, count: n + 1), count: n + 1)
    let lastYear = readLine()!.split(separator: " ").map { Int(String($0))! }
    
    // 작년 순위를 받아서 이차원 배열 및 간선 갯수 저장
        // i는 승자의 index i ~ (n - 1)은 패자의 index
    for i in 0..<(n - 1) {
        let winner = lastYear[i]
        for j in (i + 1)..<n {
            let loser = lastYear[j]
            // 승-패 관계를 이차원 배열에 저장하고 들어오는 간선 갯수 저장
            matrix[winner][loser] = true
            indegree[loser] += 1
        }
    }
    
    // 순위가 변경된 내용 indegree와 matrix에 반영하기
    let m = Int(readLine()!)!
    for _ in 0..<m {
        let ab = readLine()!.split(separator: " ").map { Int(String($0))! }
        let a = ab[0], b = ab[1]
        // 승-패 바꾸고 indegree도 반대로 설정
        if matrix[a][b] {
            matrix[a][b] = false
            matrix[b][a] = true
            indegree[b] -= 1
            indegree[a] += 1
        } else {
            matrix[b][a] = false
            matrix[a][b] = true
            indegree[a] -= 1
            indegree[b] += 1
        }
    }
    
    // 올해 순위를 저장할 배열
    var result = [Int]()
    
    // 위상 정렬 알고리즘을 위한 queue
    var queue = Queue()
    
    // indegree가 0인 vertex를 Queue에 넣는다.
    for i in 1..<(n + 1) {
        if indegree[i] == 0 {
            queue.push(i)
        }
    }
    
    // cycle이 생겨서 불가능한 경우 (= 일관성이 없는 정보)
    var impossible = false
    // queue에 vertex가 2개 이상 있는 경우 (= 확실한 올해 순위를 만들 수 없는 경우)
    var moreThanOne = false
    
    // vertex 갯수 만큼 반복하면서 순위 정하기
    for _ in 0..<n {
        if queue.isEmpty {
            impossible = true
            break
        }
        
        if queue.count > 1 {
            moreThanOne = true
            break
        }
        
        // 현재 queue에 있는 것
        let now = queue.pop()
        result.append(now)
        
        // now와 연결된 간선 정보를 삭제
        for j in 1..<(n + 1) {
            if matrix[now][j] {
                indegree[j] -= 1
                // indegree가 0이 되면 queue에 넣는다.
                if indegree[j] == 0 {
                    queue.push(j)
                }
            }
        }
    }
    
    // 결과 출력
    if impossible {
        print("IMPOSSIBLE")
    } else if moreThanOne {
        print("?")
    } else {
        print(result.map { String($0) }.joined(separator: " "))
    }
}