[Algorithm] 백준 - 2252번 줄세우기 (Swift) (위상정렬)

문제 소개

 

문제 풀이

위상정렬을 활용하였다. Kahn 알고리즘과 DFS를 활용한 위상정렬이 있다.

Kahn 알고리즘

Kahn 알고리즘은 진입차수를 계산하면서 진입차수가 0인 것을 queue에 차례로 넣는다. 진입차수라고 하면 아래와 같이 들어오는 화살표의 갯수이다.

1을 큐에 넣는다.

1을 pop하게 되면 진입차수가 0인 2, 3을 큐에 넣는다.

2를 pop하게 되면 진입차수가 0이 된 4를 추가로 queue에 넣는다.

3을 pop하게 되면 차수가 0인 5를 넣는다.

4를 pop하게 되면 차수가 0인 정점이 없으므로 아무것도 넣지 않는다.

5를 pop할때 진입차수가 0인 6을 queue에 넣는다.

6을 pop하고 마무리한다.

DFS 알고리즘

dfs 탐색을 거꾸로 하면 위상정렬이 된다. dfs 탐색을 하는데 dfs 를 한 뒤 마지막 정점을 stack에 저장해둔뒤 마지막 요소부터 꺼내면 그것이 위상정렬이 되는 것이다.

끝 정점까지 가면 6이다

그다음 끝은 5

그다음 끝은 3

그다음 끝은 1이아닌 4로 이어진다.

그다음 끝은 2

마지막 요소인 1을 넣는다

여기서 6 5 3 4 2 1 을 거꾸로 한 1 2 4 3 5 6 이 위상정렬을 한 결과가 된다.
 

문제 풀이 코드

Kahn 알고리즘 활용

import Foundation

let nm = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m) = (nm[0], nm[1])
var vertices = Array(repeating: [Int](), count: n+1)
var inDegree = Array(repeating: 0, count: n+1)

for _ in 0..<m {
    let ab = readLine()!.split(separator: " ").map { Int($0)! }
    let (a, b) = (ab[0], ab[1])
    
    vertices[a].append(b)
    inDegree[b] += 1
}

var queue = [Int]()
var idx = 0

// 진입 차수가 0인 정점 추가
for i in 1...n {
    if inDegree[i] == 0 {
        queue.append(i)
    }
}

var answer = ""

// 진입차수를 줄여가며 진입차수가 0이 되었을때 queue에 추가
while queue.count > idx {
    let popped = queue[idx]
    answer += "\(popped) "
    idx += 1
    
    for vertex in vertices[popped] {
        inDegree[vertex] -= 1
        if inDegree[vertex] == 0 {
            queue.append(vertex)
        }
    }
}

print(answer)

 

DFS 활용

import Foundation

let nm = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m) = (nm[0], nm[1])
var vertices = Array(repeating: [Int](), count: n + 1)

for _ in 0..<m {
    let ab = readLine()!.split(separator: " ").map { Int($0)! }
    let (a, b) = (ab[0], ab[1])
    vertices[a].append(b)
}

var visited = Array(repeating: false, count: n + 1)
var stack = [Int]()

// dfs 마지막에 vertex 추가
func dfs(_ v: Int) {
    visited[v] = true
    for vertex in vertices[v] {
        if !visited[vertex] {
            dfs(vertex)
        }
    }
    stack.append(v)
}

// 모든 정점에 대해서 dfs() 실행
for i in 1...n {
    if !visited[i] {
        dfs(i)
    }
}

// stack 거꾸로 출력
var answer = ""
while !stack.isEmpty {
    answer += "\(stack.removeLast()) "
}

print(answer)

 

결과

아래는 입출력 라이브러리를 사용한 경우이고, 위는 readLine()!으로 했을 때다.

 
아래는 DFS를 사용했을때 140ms, Kahn's 알고리즘을 사용했을 때 160ms로 이 문제에 한해서는 비슷한 속도를 보여줬다.