백준 2252 줄 세우기

출처: https://www.acmicpc.net/problem/2252

분류: 위상정렬

---

접근방식

위상정렬로 해결할 수 있는 문제였습니다 :)

특정 순서를 지켜야 하고 방향성 있는 그래프 일 때는 위상정렬!! 을 다시 한번 기억해야겠습니다.

 

해결방법

큐를 구현하긴 귀찮고 removeFirst도 사용하기 싫어서 큐 인덱스를 가리키는 변수를 하나 만들어서 

FIFO를 구현해봤습니다 :)

protocol Readable {
    func readSingleValue() -> String
    func readArray(with separator: Character) -> [String]
}

extension Readable {
    func readSingleValue() -> String {
        return readLine()!
    }
    
    func readSingleValue() -> Int {
        return Int(readLine()!)!
    }
    
    func readArray(with separator: Character) -> [String] {
        return readLine()!.split(separator: " ").map { String($0) }
    }
    
    func readArray(with separator: Character) -> [Int] {
        return readLine()!.split(separator: " ").map { Int(String($0))! }
    }
}

class BOJ2252_줄세우기: Readable {
    
    func input() {
        let data: [Int] = readArray(with: " ")
        n = data[0]
        entrie = [Int](repeating: 0, count: n+1)
        degrees = [[Int]](repeating: [Int](), count: n+1)
        for _ in 0..<data[1] {
            let nodes: [Int] = readArray(with: " ")
            degrees[nodes[0]].append(nodes[1])
            entrie[nodes[1]] += 1
        }
    }
    
    // MARK: Properties
    
    var n: Int!
    var degrees: [[Int]]!
    var entrie: [Int]!
    
    // MARK: Solution
    
    func solution() {
        input()
        var zeroQueue = [Int]()
        var queuePointer = 0
        var ordered = [Int]()
        
        for (zeroEntry, enter) in entrie.enumerated() where enter == 0 && zeroEntry != 0 {
            zeroQueue.append(zeroEntry)
        }
        
        while queuePointer < zeroQueue.count {
            let node = zeroQueue[queuePointer]
            queuePointer += 1
            ordered.append(node)
            degrees[node].forEach { degree in
                entrie[degree] -= 1
                if entrie[degree] == 0 {
                    zeroQueue.append(degree)
                }
            }
        }
        
        print(ordered.reduce(into: "", { $0 += "\($1) "}).dropLast())
    }
}

BOJ2252_줄세우기().solution()

 

배운점

위상정렬이 희미해져갈 때쯤 아주 적절한 문제네요 :) 

제대로 복습했습니다 !