https://www.acmicpc.net/problem/1766
1부터 N까지 난이도의 문제를 낮은 문제부터 풀되 먼저 푸는것이 좋은 문제들은 선행 문제를 풀고난 다음 후행 문제를 푼다.
이후 문제 풀이 순서를 구해 출력하는 문제이다.
입력에서 항상 문제를 모두 풀 수 있는 경우만 입력으로 주어진다 하였으므로 먼저 푸는것이 좋은 문제들은 사이클이 생기지 않는다 가정할 수 있고, 위상 정렬 개념을 적용할 수 있다.
위상 정렬은 순서가 정해진 작업을 차례대로 수행할 때 사용하는 알고리즘으로, 자신에게 오는 화살표 개수를 진입차수라는 개념으로 반복적으로 진입차수가 0인 정점을 삽입하는 방식이다.
이에 대한 예시를 하나 들어보자.
위와 같은 순서관계가 정의되었다 가정해보자.
최초 경우에서 진입차수(자신에게 오는 화살표 개수)에 대한 표를 작성해보면
| 1 | 2 | 3 | 4 |
|---|---|---|---|
| 0 | 1 | 1 | 1 |
여기서 진입차수가 0인 점인 1번 정점을 시작점으로 하고(큐에 넣고), 1번 정점을 꺼내고 1번부터 출발하는 화살표들을 지운 후 2번과 3번의 진입차수를 1씩 낮춘다. (이후 2번과 3번을 큐에 넣는다)
| 1 | 2 | 3 | 4 |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
그러면 2번과 3번 정점의 진입차수가 0으로 되어, 다시 2번과 3번으로부터 나가는 화살표를 제거하고 그 대상의 진입차수를 낮추는 과정을 반복한다.
그러면 큐 기준으로 빼내는 순서는 1 - 2 - 3 - 4가 되며 순서를 만족하게 된다.
이 개념을 그대로 적용하여 문제를 풀 수 있다.
fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
val (N, M) = readLine().split(' ').map{it.toInt()}
val precedes = IntArray(N+1){0}
val link = mutableMapOf<Int, MutableList<Int>>()
val pq = PriorityQueue<Int>()
for(i in 1..M){
val line = readLine().split(' ').map{it.toInt()}
precedes[line[1]]++
if(link[line[0]] == null)
link[line[0]] = mutableListOf()
link[line[0]]!!.add(line[1])
}
for(i in 1 until precedes.size){
if(precedes[i] == 0)
pq.add(i)
}
val answer = StringBuilder()
while(pq.isNotEmpty()){
val next = pq.poll()
link[next]?.forEach {
precedes[it]--
if(precedes[it] == 0)
pq.add(it)
}
answer.append("$next ")
}
print(answer.toString())
}precedes는 각 정점의 진입차수를 나타내는 일차원 배열입니다.
(인덱스 i에 대해 i번 정점으로 화살표가 몇 개 들어오는지 정보)
link는 한 정점에서 어떤 정점으로 화살표가 나가는지 정보를 담은 Map입니다.
(key로 i를 넣으면 i번째 정점으로부터 연결된 정점들의 list를 얻음)
첫 for문에서 각 점의 진입차수와 연결정보를 입력받아 저장함.
두번째 for문에서 최초 진입차수가 0인 점들을 queue에 넣음.
(priority queue를 사용하여 동등한 문제에 대해 난이도 낮은 문제 먼저 풀도록)
queue가 비지 않는동안 반복적으로 진입차수가 0인 정점들에 대해 해당 정점에 연결된 정점들의 진입차수를 1씩 낮추고, 0이 된다면 큐에 넣음을 반복.
(1번 점부터 2, 3번 점으로 연결되어 있다면 2번 3번 정점의 진입차수를 1로 낮추고 차수가 0이 된다면 큐에 넣음을 반복)
큐에서 뽑은 순서가 곧 풀이순서이다.
