만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 1766 문제집

23 Jun 2021

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

모든 문제를 다음 조건을 가지고 푸려고 한다.

  1. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
  2. 가능하면 쉬운 문제부터 풀어야 한다.

숫자가 낮을 수록 쉬운 문제라고 했을 때 모든 문제를 푸는 순서를 출력하는 문제이다.

선행 조건이 있기 때문에 위상정렬을 사용해야 한다는 것을 알아차릴 수 있다. 1번의 경우 위상정렬을 쓰기만 하면 해결되는데 2번의 경우는 어떻게 해야할지 난감할 수 있다.

위상이 0인 정점을 저장하는 큐를 우선순위큐로 구현을 해보면 간단하다. 위상이 0인 정점간에서 정점 index가 낮은 것이 먼저 나올 것이기 때문에 2번 조건을 만족시킬 수 있다.


struct PriorityQueue<T>{
    private var arr:[T]
    private var compare:(T, T) -> Bool
    public var isEmpty:Bool {
        return arr.isEmpty
    }
    public var count:Int {
        return arr.count
    }
    mutating func shiftUp(_ a: Int) {
        var i = a
        while i > 0 {
            let p = (i-1)/2
            if compare(arr[i], arr[p]) {
                arr.swapAt(i, p)
                i = p
            }
            else {
                break
            }
        }
    }
    mutating func shiftDown(_ a: Int) {
        var i = a
        var c = 2*i+1
        while c < arr.count {
            if c+1 < arr.count && compare(arr[c+1], arr[c]) {
                c = c+1
            }
            if compare(arr[c], arr[i]) {
                arr.swapAt(c, i)
                i = c
                c = 2*i+1
            }
            else {
                break
            }
        }
    }
    mutating func insert(_ a: T) {
        arr.append(a)
        shiftUp(arr.count-1)
    }
    mutating func pop() -> T? {
        if arr.isEmpty {
            return nil
        }
        else {
            arr.swapAt(0, arr.count-1)
            let result = arr.popLast()
            shiftDown(0)
            return result
        }
    }
    init(arr: [T] = [], compare: @escaping (T, T) -> Bool) {
        self.arr = arr
        self.compare = compare
    }
}

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0], m = nm[1]
var edge:[[Int]] = Array(repeating: [], count: n+1)
var inedge:[Int] = Array(repeating: 0, count: n+1)
var pq = PriorityQueue<Int>(compare: <)
for _ in 0..<m {
    let line = readLine()!.split(separator: " ").map{Int(String($0))!}
    let S1 = line[0], S2 = line[1]
    edge[S1].append(S2)
    inedge[S2] += 1
}
for i in 1...n {
    if inedge[i] == 0 {
        pq.insert(i)
    }
}

var str = ""
while !pq.isEmpty {
    let curr = pq.pop()!
    str += "\(curr) "
    for e in edge[curr] {
        inedge[e] -= 1
        if inedge[e] == 0 {
            pq.insert(e)
        }
    }
}
print(str)

Related posts