백준 - 줄 세우기 (2252)

let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
let (N, M) = (input[0], input[1])
var graph: [[Int]] = Array(repeating: [], count: N+1)
var indegree = Array(repeating: 0, count: N+1)
var stack = [Int]()
var answer = ""

// 인접 리스트 만들기 & 진입차수 계산
for _ in 0..<M {
    let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
    graph[input[0]].append(input[1])
    indegree[input[1]] += 1
}

// 진입차수 0인 노드 스택에 삽입
for i in 1...N {
    if indegree[i] == 0 {
        stack.append(i)
    }
}

// 위상정렬 수행
while !stack.isEmpty {
    let now = stack.removeLast()
    answer += "\(now) "
    for node in graph[now] {
        indegree[node] -= 1
        if indegree[node] == 0 {
            stack.append(node)
        }
    }
}

print(answer)

학생 A가 학생 B의 앞에 서야 하며, 답이 여러 가지가 나올 수 있다는 점에서 위상정렬 알고리즘을 사용할 수 있음을 알 수 있다.

키를 비교한 값을 가지고 인접 리스트를 만든 후 이를 사용해서 위상정렬 알고리즘을 적용해서 답을 구하면 된다.