[백준][Kotlin] 2252번 줄 세우기

해당 문제는 위상 정렬을 이용하여 작성 할 수 있는 문제 였습니다.

 

위상 정렬 (Topological sorting)은 유향 그래프에서 정점들을 순서대로 나열하는 것을 말합니다. 이때, 그래프에서 간선은 항상 정점들 사이의 의존 관계를 나타내며, 위상 정렬은 이러한 의존 관계를 지켜가며 모든 정점을 나열하는 작업입니다.

위상 정렬의 핵심 아이디어는 "진입 차수(in-degree)" 개념입니다. 정점의 진입 차수란 그래프에서 들어오는 간선의 수를 의미합니다. 위상 정렬에서는 진입 차수가 0인 정점을 선택하여 정렬 순서에 추가하고, 이 정점과 연결된 간선을 제거한 뒤에 남은 그래프에서 다시 진입 차수가 0인 정점을 선택하여 반복적으로 정렬합니다.

만약, 그래프가 사이클을 포함하고 있다면, 위상 정렬을 할 수 없습니다. 이는 사이클이 있을 경우에는 위상 정렬로 정렬할 수 있는 최소한의 정점 수를 찾을 수 없기 때문입니다.

위상 정렬은 컴파일러의 의존성 분석이나 작업 스케줄링 등 다양한 분야에서 활용됩니다. 위상 정렬의 시간 복잡도는 O(V+E)입니다.

 

하기는 제가 작성한 코드와 제출 결과 입니다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.collections.ArrayList

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()

    var degree = IntArray(n+1,{0}) // 진입차수를 저장 할 배열
    var next = Array(n+1, {ArrayList<Int>()}) // 현재 노드에서 갈 수 있는 노드리스트 저장할 배열
    repeat(m){
        st = StringTokenizer(br.readLine())
        var front = st.nextToken().toInt() // 앞에 있어야 할 숫자
        var back = st.nextToken().toInt() // 뒤에 있어야 할 숫자
        degree[back]++
        next[front].add(back)
    }

    var dq = ArrayDeque<Int>()
    for(i in 1 .. degree.size-1){
        if(degree[i] == 0) {
            dq.add(i)
        }
    }

    while(!dq.isEmpty()){
        val now = dq.pollFirst()
        bw.append("$now ")
        for(i in next[now]){
            degree[i]--
            if(degree[i] == 0){
                dq.addLast(i)
            }
        }
    }

    bw.flush()
    bw.close()
}