[백준/BOJ] 1766번: 문제집

문제

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

1766번: 문제집

해설

문제들의 선행 순서를 입력으로 받고, 이를 이용하여 순서를 짜야한다.

또한 문제의 난이도는 1번 문제가 가장 쉽고 N번 문제가 가장 어려우며, 가능한 쉬운 문제부터 문제를 풀어야 한다.

 

이러한 유형의 문제는 위상 정렬을 이용하여 해결할 수 있다.

위상 정렬을 이용하나, 이 문제에서는 문제의 난이도까지 고려해야하고, 이는 문제의 번호가 낮을수록 쉽우므로 우선순위 큐를 사용하면 쉽게 해결할 수 있다.

코드

import java.util.*
import kotlin.collections.ArrayList

private lateinit var degree: IntArray
private val graph = ArrayList<ArrayList<Int>>()

fun main() = with(System.`in`.bufferedReader()) {
    val (problemCnt, infoCnt) = readLine().split(" ").map { it.toInt() }
    degree = IntArray(problemCnt + 1)

    repeat(problemCnt + 1) {
        graph.add(ArrayList())
    }

    repeat(infoCnt) {
        val priority = readLine().split(" ").map { it.toInt() }
        graph[priority[0]].add(priority[1])
        degree[priority[1]]++
    }

    topologicalSort(problemCnt)
}

private fun topologicalSort(n: Int) {
    val result = ArrayList<Int>()
    val pq = PriorityQueue<Int>()

    for(i in 1 .. n) {
        if(degree[i] == 0) pq.add(i)
    }

    while(pq.isNotEmpty()) {
        val cur = pq.poll()
        result.add(cur)

        for(next in graph[cur]) {
            degree[next]--

            if(degree[next] == 0) pq.add(next)
        }
    }

    for(i in result) print("$i ")
}