[정렬] 줄 세우기 - 백준 2252번 Swift

문제 : https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

위상정렬 문제이다. 

위상 정렬이란 어떤 일을 하는 순서를 찾는 알고리즘이다.

즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것

개념 -> https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html

[알고리즘] 위상 정렬(Topological Sort)이란 - Heee's Development Blog

 

요약해서 설명하자면

1. 진입차수가 0인것만 큐에 넣는다.
2. 큐에서 1개를 꺼내고 거기에 연결된 간선을 제거한다.
3. 간선을 제거하다가 진입차수가 0이되는 순간 큐에 다시 넣는다.
4. 큐가 빌 때 까지 위의 과정반복
5. 이문제는 진입차수가 0이 되는 노드순으로 배열을 만들어서 반환하면 되는 문제이다.

 

코드

import Foundation

var n = 0
var degree = [Int]()
var entrie: [Int]!
var infomation: [[Int]]!

func sol() {
    var firstInput = readLine()!.components(separatedBy: " ").map{Int($0)!}
    var zeroQueue = [Int]()
    n = firstInput[0]
    entrie = [Int](repeating: 0, count: n+1)
    infomation = [[Int]](repeating: [Int](), count: n+1)
    var result = [Int]()
    
    var queuePointer = 0

    for index in 0..<firstInput[1] {
        let nodes: [Int] = readLine()!.components(separatedBy: " ").map{Int($0)!}
        infomation[nodes[0]].append(nodes[1])
        entrie[nodes[1]] += 1
    }
    
    for (zeroEntryIndex, enter) in entrie.enumerated() where enter == 0 && zeroEntryIndex != 0 {
            zeroQueue.append(zeroEntryIndex)
    }
    
    print(zeroQueue)
    print(infomation)
    while queuePointer < zeroQueue.count {
             let node = zeroQueue[queuePointer]
             queuePointer += 1
             result.append(node)
             infomation[node].forEach { degree in
                 entrie[degree] -= 1
                 if entrie[degree] == 0 {
                     zeroQueue.append(degree)
                 }
             }
         }
    
    print(result.reduce(into: "", { $0 += "\($1) "}))
}

sol()

 

출처 및 참고

https://woongsios.tistory.com/218

백준 2252 줄 세우기