줄세우기.md

줄 세우기

위상정렬, Topological Sort

순서가 정해져있는 작업을 차례대로 수행할 때 그 순서를 결정해주기 위해 사용하는 알고리즘

DAG(Directed Acyclic Graph)

비순환 그래프여야 하며 시작점이 있어야 한다.

Queue, stack으로 구현

O(V + E)

import Foundation

let input = readLine()!.split(separator: " ").map({ Int(String($0))! })
let n = input[0]
let t = input[1]
var adj = Array(repeating: [Int](), count: n+1)
var inDegree = Array(repeating: 0, count: n+1) // 진입차수
for _ in 0..<t {
    let input = readLine()!.split(separator: " ").map({ Int(String($0))! })
    let v = input[0]
    let w = input[1]
    adj[v].append(w)
    inDegree[w] += 1 
}

var queue = [Int]()

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

for _ in 1..<n+1 {
    if queue.isEmpty {
        print("이건 위상정렬 쓰면 안됨니다🚥")
        break
    }
    let x = queue.removeFirst()
    print(x)
    for j in 0..<adj[x].count {
        let y = adj[x][j]
        inDegree[y] -= 1
        if inDegree[y] == 0 {
            queue.append(y)
        }
    }
}

DFS - 메모리초과

아마

let input = readLine()!.split(separator: " ").map({ Int(String($0))! })
let n = input[0]
let t = input[1]

var adj = Array(repeating: Array(repeating: 0, count: n+1), count: n+1)
var visited = Array(repeating: false, count: n+1)

for _ in 0..<t {
    let input = readLine()!.split(separator: " ").map({ Int(String($0))! })
    let v = input[0]
    let w = input[1]
    adj[v].append(w)
}

var result = [Int]()
var stack = [Int]()

func dfs(_ i: Int) {
    visited[i] = true
    for j in 1..<adj[i].count {
        let next = adj[i][j]
        if !visited[next] {
            dfs(next)
        }
    }
    stack.append(i)
}

for i in 1..<n+1 {
    if !visited[i] {
        dfs(i)
    }
}

while stack.count > 1 {
    print(stack.popLast()!)
}