[알고리즘] 줄 세우기 (백준 2252번)

2252번: 줄 세우기

 N, M의 크기만 봐도 알 수 있지만 그래프 완전탐색 문제이며 N은 정점, M은 간선의 수를 나타낸다. 정확히는 위상 정렬 문제다. 각 노드보다 앞서 있는 노드들이 먼저 출력되어야 하는 형태를 가진다.

 

Solution

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


var br = BufferedReader(InputStreamReader(System.`in`))
var bw = BufferedWriter(OutputStreamWriter(System.out))


fun solution() {

    var N = 0
    var M = 0
    br.readLine()!!.split(" ").forEachIndexed { index, s ->
        if(index == 0)
            N = s.toInt()
        else
            M = s.toInt()
    }

    var graph = ArrayList<ArrayList<Int>>()
    graph.apply {
        for(i in 0..N)
            add(ArrayList())
    }

    var in_edges = IntArray(N + 1)

    for(i in 0 until M)
    {
        var list = br.readLine()!!.split(" ")
        var from = list[0].toInt()
        var to = list[1].toInt()

        graph[from].add(to)
        in_edges[to] ++
    }

    var queue : Queue<Int> = LinkedList()

    in_edges.forEachIndexed { index, i -> if(index > 0 && i == 0) queue.offer(index) }

    while(!queue.isEmpty())
    {
        var now = queue.poll()

        bw.write("$now ")

        for(j in 0 until graph[now].size)
        {
            var next = graph[now][j]
            in_edges[next] --

            if(in_edges[next] == 0)
                queue.offer(next)

        }
    }
}



fun main() {
    solution()
    br.close()
    bw.close()

}