[백준 1766] - 문제집(Kotlin)[골드2]

문제

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

1766번: 문제집

 

문제 풀이

문제의 조건을 고려하면서 어떻게 풀지 고민을 하면 위상정렬과 굉장히 유사하다는 것을 알 수 있다.

위상정렬에 정의는 순서가 있는 작업을 차례로 진행할 때, 순서를 결정하는 알고리즘이다.

문제에서 대놓고 문서를 풀 순서를 정하는 키워드가 있기도하다.

 

해당 문제에서 문제를 정하는 조건은 다음과 같다.

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있다면 반드시 먼저 풀어야 한다.
3. 가능한 쉬운 문제부터 풀어야 한다.

 

2번 조건과 3번 조건이 문제에서 중요한 조건이라고 할 수 있다.

2번 조건을 통해서 우리는 문제 간의 부모 자식과 같이 관계가 존재하고, 해당 관계가 상위 문제가 풀려야 하위 문제를 풀 수 있음을 알 수 있다.

그리고 3번 조건을 통해서 같은 우선순위의 문제라도, 반드시 숫자가 적은(난이도가 쉬운) 문제를 풀어야 함을 알 수 있다.

 

이러한 조건을 바탕으로 나는 우선순위큐를 사용한 위상정렬로 문제를 풀었다.

기존 위상정렬의 기본 문제들은 stack이나 queue를 사용하는 문제가 많았지만, 해당 문제들은 답이 여러 개인 문제가 많았지만,

해당 문제는 쉬운 문제부터 풀어야 하는 조건 때문에 답이 명확하게 하나였고, 그를 우선순위큐를 통해서 풀었다.

 

inDegree 결정하기

입력은 A B로 주어지는데 A가 B보다 먼저 풀어야 하는 문제이다.

즉 B는 A를 풀어야 풀 수 있고, 자신보다 선행되어야 할 문제들의 개수를 inEdge로 더해줬다.

관계가 아닐 정점 간의 메모리 할당은 불필요하기 때문에 graph는 인접리스트로 구현했다.

repeat(m) {
    br.readLine().split(" ").map { it.toInt() }.apply {
        graph[this[0]].add(this[1])
        inEdge[this[1]]++
    }
}

 

먼저 풀어야 할 문제 정하기

압도적으로 먼저 풀어야 할 문제는 자신보다 먼저 풀어야 할 문제가 없는 문제들이다.

이들은 inEdge의 값이 0이다.

따라서 inEdge 값이 0인 정점들을 큐에 넣어줘야 했고, 우선순위큐를 통해서 난이도 별로 정렬할 수 있게 구현했다.

val q: PriorityQueue<Int> = PriorityQueue()
for (i in 1..n) {
    if (inEdge[i] == 0) {
        q.add(i)
    }
}

 

문제 순서 정하기

queue에 들어있는 원소들은 순서가 정해져 있는 문제들이다.

now에 대해서 now와 연결된 문제들을 순회하면서 다음을 검사한다.

now를 풀었기 때문에 now와 연결된 정점들의 inEdge를 감소시켜 준다.

inEdge가 0인 정점들은 이제 풀 수 있는 문제들이기에 q에 넣어준다.

while (!q.isEmpty()) { //q에 들어간 원소들은 inEdge가 0인 놈들
    val now = q.poll()
    sb.append(now).append(" ")
    for (i in 0 until graph[now].size) {
        val connectVertex = graph[now][i]
        inEdge[connectVertex]--
        if (inEdge[connectVertex] == 0) { //이제 연결된 간선이 없을 경우
            q.add(connectVertex)
        }
    }
}

전체 코드

import java.lang.StringBuilder
import java.util.PriorityQueue


class Solution {

    private val br = System.`in`.bufferedReader()
    private var n = 0
    private var m = 0
    private lateinit var graph: Array<ArrayList<Int>>
    private lateinit var inEdge: IntArray
    private val sb = StringBuilder()

    fun run() {
        input()
        solve()
        println(sb.toString())
    }

    private fun input() {
        br.readLine().split(" ").map { it.toInt() }.apply {
            n = this[0]
            m = this[1]
        }
        graph = Array(n + 1) { arrayListOf() }
        inEdge = IntArray(n + 1)
        repeat(m) {
            br.readLine().split(" ").map { it.toInt() }.apply {
                graph[this[0]].add(this[1])
                inEdge[this[1]]++
            }
        }
    }

    private fun solve() {
        val q: PriorityQueue<Int> = PriorityQueue()
        for (i in 1..n) {
            if (inEdge[i] == 0) {
                q.add(i)
            }
        }

        while (!q.isEmpty()) { //q에 들어간 원소들은 inEdge가 0인 놈들
            val now = q.poll()
            sb.append(now).append(" ")
            for (i in 0 until graph[now].size) {
                val connectVertex = graph[now][i]
                inEdge[connectVertex]--
                if (inEdge[connectVertex] == 0) { //이제 연결된 간선이 없을 경우
                    q.add(connectVertex)
                }
            }
        }
    }
}

fun main() {
    val solution = Solution().run()
}