[백준/BOJ] 2252번: 줄 세우기

문제

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

2252번: 줄 세우기

해설

문제의 답이 여러 개일 수 있는 스페셜 저지 문제이다.

처음에 어떻게 푸나 고민하다, 위상 정렬을 이용해서 풀었다는 글들을 많이 보았다.

위상 정렬이란 "선후 관계가 정의되 있는 그래프 구조 상에서 그에 따라 정렬하는 방법"이다.

 

문제의 예제1을 보면서 위상 정렬의 과정을 봐보자.

위상 정렬에는 큐를 사용하고, 또한 그래프 구조 상에서 정렬하는 방법이기에 그래프 형식을 선언해준다.

 

1번 학생 뒤에 3번 학생이 오고 2번 학생의 뒤에 3번 학생이 온다고 되있다.

누군가의 뒤에 선다는 것을 저장하기 위한 배열 order를 선언해주자.

3번 학생은 1번 학생의 뒤에 서야하므로 order[3]++을 해주고, graph[1].add(3)을 해준다.

다음으로 3번 학생은 2번 학생보다도 뒤에 서야한다. 또 한번 order[3]++을 해주자.

그렇다면 order[1] = 0, order[2] = 0, order[3] = 2가 된다.

여기까지만 봐도 답은 1 - 2 - 3 또는 2 - 1 - 3이다. 둘 다 정답 처리가 된다.

 

답은 알지만 이를 순서대로 뽑는 법을 보도록 하자.

우선 값이 0이라는 것은 앞에 아무도 없거나, 누가 서는지 모르는 것이다.

따라서 0인 것들을 큐에 넣어준다.

 

모두 넣었다면 큐가 빌 때까지 반복을 할 것이다.

첫번째로 큐에 들어 있는 값은 1일 것이다.

이 값을 poll해주고 StringBuilder에 담아준다. 1에 연결된 사람은 3이 된다. 3의 값을 --를 해주면 2에서 1로 된다. 아직 앞에 1명이 더 있다는 것이다.

이후 2가 poll이 되고 2와 연결된 3이 또 한번 --가 되면서 0이 된다. 이제 3의 앞에 더 이상 설 사람이 없다는 의미이다.

코드

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

private lateinit var compare: Array<ArrayList<Int>>
private lateinit var order: IntArray

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

    compare = Array(n + 1) { ArrayList() }
    order = IntArray(n + 1)

    repeat(m) {
        val (a, b) = readLine().split(" ").map { it.toInt() }
        compare[a].add(b)
        order[b]++
    }

    solution()
}

private fun solution() {
    val sb = StringBuilder()
    val que: Queue<Int> = LinkedList()

    for(i in 1 until order.size) {
        if(order[i] == 0) que.add(i)
    }

    while(que.isNotEmpty()) {
        val cur = que.poll()
        sb.append("$cur ")

        for(i in compare[cur].indices) {
            val next = compare[cur][i]
            order[next]--

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

    println(sb.toString())
}