[알고리즘/Swift] 2252 줄 세우기

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 2252 줄 세우기
• 제출 언어: Swift
• 알고리즘 분류:
  • 그래프 이론
  • 위상 정렬

---

풀이

위상 정렬

• 그래프 내의 모든 정점(node)를 선형으로 정렬할 때 사용한다
• cycle이 없는 조건일 경우 사용한다
• 모든 간선(u,v)의 node u가 node v보다 먼저 오도록 정렬하는 알고리즘이다

알고리즘 적용

• indegree 배열에 모든 node들로 들어오는 간선의 개수를 저장한다
• indegree가 0인 node를 시작 node로 지정하고 queue에 넣어준다
• queue가 비어있을 때까지 하나씩 꺼내서 그 node가 들어가는 간선의 도착 node의 indegree를 1씩 빼준다
• 이 후 indegree가 0이 된 node가 있다면 다시 queue에 넣어준다
  이러한 알고리즘을 통해 간선으로 연결되어 있는 정점들이 순서대로 정렬할 수 있다
  
  

---

전체 코드

import Foundation

let n = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (n[0], n[1])
var arr: [[Int]] = Array(repeating: [], count: N+1)
var inDegree = Array(repeating: 0, count: N+1)
var queue = Array<Int>()
var result = Array<Int>()
for i in 0..<M{
    let m = readLine()!.split(separator: " ").map{Int(String($0))!}
    let (A, B) = (m[0], m[1])
    arr[A].append(B)
    inDegree[B] += 1
}

for i in 1...N{
    if inDegree[i] == 0{
        queue.append(i)
    }
}

while !queue.isEmpty{
    var current = queue.remove(at: 0)
    result.append(current)
    
    for i in arr[current]{
        inDegree[i] -= 1
        
        if inDegree[i] == 0{
            queue.append(i)
        }
    }
}
for i in result{
    print(i, terminator: " ")
}