개요
위상 정렬(Topological Sort)은 방향 그래프에서 정점을 선형적으로 나열하는 알고리즘입니다. 이 알고리즘은 주로 작업의 의존성을 표현하는 문제에 맞게 사용됩니다. 예를 들어, 과목 이수도, 태스크 스케줄링 등 다양한 문제를 해결하는 데 유용합니다.
문제 설명
다음은 위상 정렬을 활용한 문제입니다.
문제: 과목 이수 문제
대학교에서 과목 A를 이수하기 위해 반드시 이수해야 하는 과목 B와 C가 있습니다. 여러 과목과 이수 조건이 주어질 때, 모든 과목을 이수하기 위한 수업 순서를 구하는 프로그램을 코틀린으로 작성하세요. 과목의 수업 순서는 여러 가지가 될 수 있습니다. 가능한 모든 수업 순서를 반환하는 것이 목표입니다.
입력 형식
- 첫 번째 줄에 정수 N (1 ≤ N ≤ 20): 과목의 개수
- 두 번째 줄에 정수 M (0 ≤ M ≤ 100): 이수 조건 쌍의 개수
- 다음 M줄에는 ‘A B’ 형태로 각 줄마다 이수 조건을 의미하는 정수 두 개가 주어집니다. ‘A’ 과목을 끝내기 위해서는 ‘B’ 과목을 먼저 이수해야 합니다.
출력 형식
과목의 이수 순서를 공백으로 구분하여 한 줄에 출력합니다. 가능한 이수 순서가 여러 개라면, 사전 순으로 가장 빠른 과목 순서만을 출력합니다.
문제 풀이 과정
1. 문제 이해하기
문제를 해결하기 위해 먼저 위상 정렬의 개념을 이해해야 합니다. 그래프에서 정점은 과목을, 간선은 이수 조건을 나타냅니다. 이수 조건이 있어야만 이수할 수 있는 과목을 나타내는 방향 그래프를 구성할 수 있습니다.
2. 그래프 구성
문제로 주어진 과목과 이수 조건을 바탕으로 그래프를 구성합니다. 각 과목은 노드가 되고, 이수 조건은 방향 간선으로 표현됩니다.
val graph = mutableMapOf>()
val inDegree = IntArray(N + 1) // 각 과목의 진입 차수를 저장
3. 진입 차수 계산
각 과목의 진입 차수를 계산합니다. 진입 차수는 해당 과목에 도달하기 위해 먼저 이수해야 하는 과목의 개수를 의미합니다.
for (i in 0 until M) {
val a = readLine()!!.split(' ').map { it.toInt() }
graph.getOrPut(a[1]) { mutableListOf() }.add(a[0])
inDegree[a[0]]++
}
4. 위상 정렬 알고리즘 구현하기
위상 정렬은 BFS 방식으로 구현할 수 있습니다. 진입 차수가 0인 노드부터 시작하여 해당 노드를 차례대로 방문하면서 진입 차수를 줄여 나갑니다. 이 과정에서 노드가 추가로 진입 차수가 0이 되는 경우 큐에 추가합니다.
fun topologicalSort(N: Int): List {
val result = mutableListOf()
val queue: Queue = LinkedList()
// 진입 차수가 0인 노드 큐에 추가
for (i in 1..N) {
if (inDegree[i] == 0) {
queue.add(i)
}
}
while (queue.isNotEmpty()) {
// 사전 순 정렬을 위해 큐에서 정점 꺼내기
val current = queue.poll()
result.add(current)
// 현재 정점에서 나가는 간선 처리
for (next in graph[current] ?: listOf()) {
inDegree[next]--
if (inDegree[next] == 0) {
queue.add(next)
}
}
}
return result
}
5. 최종 코드
위상 정렬 기능을 포함한 최종 코드는 아래와 같습니다.
fun main() {
val (N, M) = readLine()!!.split(' ').map { it.toInt() }
val graph = mutableMapOf>()
val inDegree = IntArray(N + 1)
// 그래프 및 진입 차수 초기화
for (i in 0 until M) {
val (a, b) = readLine()!!.split(' ').map { it.toInt() }
graph.getOrPut(b) { mutableListOf() }.add(a)
inDegree[a]++
}
// 위상 정렬 수행
val result = topologicalSort(N)
// 결과 출력
println(result.joinToString(" "))
}
결론
위상 정렬은 다양한 그래프 문제를 해결하는 데 있어 매우 유용한 알고리즘입니다. 과목 이수 문제와 같이 의존 관계를 고려해야 하는 상황에서 더욱 빛을 발합니다. 이번 강좌에서는 위상 정렬의 기본 개념과 함께 문제 풀이 과정을 단계별로 살펴보았습니다. 앞으로도 다양한 알고리즘 문제를 통해 코틀린 실력을 한 단계 끌어올리시길 바랍니다.