백준 2623번 음악프로그램 - 스위프트(Swift) 풀이

1. 각 출연자를 정점으로 생각하고, 보조 PD들이 만든 순서가 A B C D라면 A→B, B→C, C→D로 가는 간선을 추가한다.
2. 완성된 그래프에 대해 위상 정렬을 한다.
3. 위상 정렬 결과에 포함된 정점 개수가 N개가 아니라면 순서를 정하는 것이 불가능한 경우이다.

---

1. 각 출연자를 정점으로 생각하고, 보조 PD들이 만든 순서가 A B C D라면 A→B, B→C, C→D로 가는 간선을 추가한다.

선행 관계가 주어진 작업들의 순서 정하기 문제이다. 위상 정렬 알고리즘을 사용하여 해결할 수 있다. 현재 상황을 그래프로 변환한다. 보조 PD들이 만든 X명의 순서를 차례로 쪼개면 X-1개의 선행 관계가 나오게 된다. 위와 같이 선행 관계로 쪼개 간선을 추가해준다.

 

2. 완성된 그래프에 대해 위상 정렬을 한다.

 위상 정렬을 수행하면 주어진 선행 관계를 위배하지 않는 정렬 결과가 나오게 된다.

 

3. 위상 정렬 결과에 포함된 정점 개수가 N개가 아니라면 순서를 정하는 것이 불가능한 경우이다.

 순서를 정하는 것이 불가능한 경우는 주어진 선행 관계 사이에 모순이 있는 경우이다. 이런 경우 그래프에 사이클이 생기게 된다. 사이클이 생기면 사이클을 이루는 정점들의 진입 차수는 절대 0이 될 수 없기 때문에 위상 정렬 결과에서 빠지게 된다. 따라서 위상 정렬 결과에 모든 정점이 포함되는지, 즉 결과의 정점 개수가 N개인지를 체크하면 순서 정하기 가능여부를 판별할 수 있다.

 

---

import Foundation

var N = 0, M = 0
var edges = Array(repeating: Array(repeating: false, count: 1001), count: 1001)
var indegree = Array(repeating: 0, count: 1001)

struct Queue {
    var queue = [Int]()
    var front = 0
    
    var isEmpty: Bool {
        return front >= queue.count
    }
    
    mutating func insert(_ n: Int) {
        queue.append(n)
    }
    
    mutating func popFront() -> Int {
        let ret = queue[front]
        front += 1
        return ret
    }
}

func topologySort() -> [Int] {
    var result = [Int]()
    var queue = Queue()
    
    for i in 1...N {
        if indegree[i] == 0 {
            queue.insert(i)
        }
    }
    
    while !queue.isEmpty {
        let current = queue.popFront()
        
        result.append(current)
        
        for end in 1...N {
            if edges[current][end] {
                indegree[end] -= 1
                if indegree[end] == 0 { queue.insert(end) }
            }
        }
    }
    
    if result.count != N { return [0] }
    else { return result }
}

func solution() {
    var input = readLine()!.split(separator: " ").map{ Int(String($0))! }
    N = input[0]
    M = input[1]
    
    for _ in 0..<M {
        input = readLine()!.split(separator: " ").map{ Int(String($0))! }
        for i in 1..<input.count-1 {
            let start = input[i]
            let end = input[i+1]
            
            if !edges[start][end] {
                edges[start][end] = true
                indegree[end] += 1
            }
        }
    }
    
    let result = topologySort()
    
    var resultString = ""
    result.forEach{ resultString.write("\($0)\n") }
    print(resultString)
}

solution()