[Kotlin] 백준 2252번 : 줄 세우기 <Gold 3>

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

Code

---

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.LinkedList
import java.util.Queue
import kotlin.math.max

fun main()  = with(BufferedReader(InputStreamReader(System.`in`))){
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val (N, M) = readLine().split(" ").map { it.toInt() }
    val graph = Array(N + 1) { mutableListOf<Int>() }
    val inDegree = IntArray(N + 1)
    val queue: Queue<Int> = LinkedList()
    val result = mutableListOf<Int>()

    repeat(M){
        val (A, B) = readLine().split(" ").map { it.toInt() }

        graph[A].add(B)
        inDegree[B]++
    }

    for (i in 1 .. N){
        if (inDegree[i] == 0) queue.add(i)
    }

    while (queue.isNotEmpty()){
        val now = queue.poll()
        result.add(now)

        for (i in graph[now]){
            inDegree[i]--

            if (inDegree[i] == 0) queue.add(i)
        }
    }

    result.forEach{
        bw.write("$it ")
    }
    bw.flush()
    bw.close()
}

---

이전에 글을 작성했던 "위상정렬"을 활용한 문제다.

 

앞에있는 숫자와 뒤에있는 숫자를 기록한다.

앞에있는 숫자의 리스트에는 뒤에 있는 숫자를 기록하고, 뒤에있는 숫자의 degree를 1 늘려준다.

 

위와같은 과정을 전부 거친다면 모든 숫자의 degree가 나온다.

degree가 0이라면 맨 앞에 있을 수 있는 숫자이다.

 

그렇기 때문에 degree가 0인 값들만 queue에 넣어준다.

queue에 넣어 둔 값들을 하나씩 꺼내며 해당 값의 뒤에 있는 숫자의 차수를 하나씩 없애준다. 이때, 해당숫자의 차수가 0이 된다면 queue에 넣어준다. 

 

이 과정을 반복하며 queue에서 꺼낸 순서대로 출력해주면 된다.

 

 

위상정렬을 활용한 문제였다. 그저 위상정렬이 뭔지를 아느냐 묻는 문제였다.

사실 나도 위상정렬이 뭔지 몰랐다. 이 문제로 위상정렬이라는 것을 알게 되었고, 공부하여서 적용했다.

 

생각보다는 쉬운 알고리즘이었다. 하지만, 활용을 하면 정말 어려울거 같은 느낌.