[백준/BOJ] 2623번: 음악프로그램

문제

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

2623번: 음악프로그램

해설

보조 PD 3명이 담당한 가수들의 순서를 정한다.

이때 한 가수를 여러 보조 PD가 담당할 수 있다.

 

이렇듯 이미 순서가 정해져 있고, 선행 순서를 위배하지 않으면서 순서를 정하는 것은 위상 정렬(topological sort) 알고리즘을 사용하면 된다.

위상 정렬은 여러 가지 답이 나올 수 있으므로, 코드를 어떻게 짜냐에 따라 답이 달라질 수 있다.

코드

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

private lateinit var graph: ArrayList<ArrayList<Int>>
private lateinit var degree: IntArray

fun main() = with(System.`in`.bufferedReader()) {
    val (singerCnt, pdCnt) = readLine().split(" ").map { it.toInt() }

    graph = ArrayList(ArrayList())
    repeat(singerCnt + 1) {
        graph.add(ArrayList())
    }

    degree = IntArray(singerCnt + 1)

    repeat(pdCnt) {
        val st = StringTokenizer(readLine())
        val cnt = st.nextToken().toInt()
        var priority = st.nextToken().toInt()

        repeat(cnt - 1) {
            val next = st.nextToken().toInt()
            graph[priority].add(next)
            degree[next]++

            priority = next
        }
    }

    topologicalSort(singerCnt)
}

private fun topologicalSort(n: Int) {
    val result = ArrayList<Int>()
    val que: Queue<Int> = LinkedList()

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

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

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

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

    if(result.size != n) println(0)

    for(i in result) println(i)
}