만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 3665 최종 순위

23 Jun 2021

https://www.acmicpc.net/problem/3665

작년 순위가 주어지고 올해 상대적인 등수가 바뀐 쌍의 수가 주어지면 올해의 새로운 순위를 출력하는 문제이다. 문제 자체에서 혼동이 와서 헤깔리기 쉬운 문제이니 유의하기 바란다.

모든 정점은 자신보다 순위가 높은 정점에서 작은 정점으로 간선이 존재한다고 하자. 예시로 ABCD 순의 등수가 주어졌다고 했을 때 그림은 다음과 같다. 위상정렬 순으로 하나씩 정점을 뽑아내면 등수 순으로 뽑아내는 것과 같다는 것을 명심하자.

3665_1

이 때 C와 A의 순위가 바뀌었다고 공개가 된다면 그림은 다음처럼 바뀔 것이다.

3665_2

해당 그림에서 위상정렬을 해보려고 보면 A, B, C 간에 사이클이 생겨서 만들어 낼 수가 없다. 일부 사람들은 하지만 C A 순위가 바뀌면 CBAD의 결과가 나와야하는것이 아닌가요? 할 수 있다. 단순히 생각하면 ABCD 에서 CBAD가 된다고 생각하기 쉽지만 그렇게 될 경우 A와 B, C와 B의 관계도 바뀌게 되는 것이므로 상대 순위 변동이 추가적으로 공개가 되야한다.

3665_3

이번에는 A B의 순위와 C B 순위도 바뀌었다고 공개가 되었다고 하자. 그럴 경우 그래프는 위와 같이 변하며 위상 정렬 순으로 뽑았을 때 정상적으로 CBAD가 나오는 것을 확인할 수 있다.

이제 이를 활용하여 순위에 따른 그래프를 설정해주고 위상정렬 알고리즘을 사용해주면 된다. 한가지 유의할 점으로는 정상적으로 순위가 나오려면 위상이 0이 되는 정점이 한번에 하나씩 등장해야 한다는 것이다. 만약 위상이 0이 되는 정점이 2개 이상이 된다면 둘 간의 순위 파악이 안된다는 의미이다. 또한 사이클이 생겨 위상정렬이 더이상 불가능해진다면 상대 순위 공개가 덜 됐다는 의미이므로 순위를 뽑아내는 것이 불가능 하다는 것을 알아야한다.

let t = Int(readLine()!)!
for _ in 1...t {
    let n = Int(String(readLine()!))!
    var priCount = Array(repeating: 0, count: n+1)
    var edge:[[Int]] = Array(repeating: [], count: n+1)
    let order = readLine()!.split(separator: " ").map{Int(String($0))!}
    for i in 0..<order.count {
        for j in 0..<i {
            edge[order[j]].append(order[i])
        }
        priCount[order[i]] = i
    }
    let m = Int(String(readLine()!))!
    for _ in 0..<m {
        let line = readLine()!.split(separator: " ").map{Int(String($0))!}
        let S1 = line[0], S2 = line[1]
        if edge[S1].contains(S2) {
            edge[S2].append(S1)
            edge[S1].remove(at: edge[S1].firstIndex(of: S2)!)
            priCount[S1] += 1
            priCount[S2] -= 1
        }
        else {
            edge[S1].append(S2)
            edge[S2].remove(at: edge[S2].firstIndex(of: S1)!)
            priCount[S2] += 1
            priCount[S1] -= 1
        }
    }
    
    var result = 0
    var str = ""
    var queue:[Int] = []
    for i in 1...n {
        if priCount[i] == 0 {
            queue.append(i)
        }
    }
    if queue.count > 1 {
        result = -1
    }
    else if queue.count == 0 {
        result = -2
    }
    else {
        while !queue.isEmpty {
            let curr = queue.removeFirst()
            str += "\(curr) "
            result += 1
            for k in edge[curr] {
                priCount[k] -= 1
                if priCount[k] == 0 {
                    queue.append(k)
                }
            }
            if queue.count > 1 {
                result = -1
                break
            }
        }
    }
    switch result {
    case -1:
        print("?")
    case n:
        print(str)
    default:
        print("IMPOSSIBLE")
    }
}

Related posts