[ 알고리즘 / Kotlin ] 위상 정렬 알고리즘

위상 정렬은 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘입니다.

백준에 나와있는 문제로 예시를 들겠습니다!

 

www.acmicpc.net/problem/1005

1005번: ACM Craft

문제

서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다.

이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다.

 

 

위의 예시를 보자.

이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 있다. (동시에 진행이 가능하다) 그리고 4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야지만 4번건물의 건설을 시작할수 있다.

따라서 4번건물의 건설을 완료하기 위해서는 우선 처음 1번 건물을 건설하는데 10초가 소요된다. 그리고 2번 건물과 3번 건물을 동시에 건설하기 시작하면 2번은 1초뒤에 건설이 완료되지만 아직 3번 건물이 완료되지 않았으므로 4번 건물을 건설할 수 없다. 3번 건물이 완성되고 나면 그때 4번 건물을 지을수 있으므로 4번 건물이 완성되기까지는 총 120초가 소요된다.

프로게이머 최백준은 애인과의 데이트 비용을 마련하기 위해 서강대학교배 ACM크래프트 대회에 참가했다! 최백준은 화려한 컨트롤 실력을 가지고 있기 때문에 모든 경기에서 특정 건물만 짓는다면 무조건 게임에서 이길 수 있다. 그러나 매 게임마다 특정건물을 짓기 위한 순서가 달라지므로 최백준은 좌절하고 있었다. 백준이를 위해 특정건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 프로그램을 작성해주자.

 

이러한 문제입니다! 이 문제는 위상 정렬 알고리즘을 사용하기 딱! 좋은 문제인데요

위의 예시로 보면 1번 건물을 다 지어야 2,3번을 지을 수 있고 2,3번 건물을 다 지어야 4번 건물을 지을 수 있는거죠

이렇듯, 건물 짓는 순서가 정해져있는 (순서가 정해져있는) 작업을 차례로 수행할 때 잘 쓰이는 알고리즘이죠

 

이러한 위상 정렬의 구현 방법에는 스택과 큐를 사용할 수 있지만, 저는 큐를 더 선호해서 큐를 이용하여 구현을 해보겠습니다!

 

위상 정렬을 구현 할 땐 네가지만 생각하시면 됩니다

1) 진입차수가 0인 정점을 큐에 삽입

2) 큐에서 원소를 꺼내 연결된 모든 간선 제거

3) 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입

4) 큐가 빌 때까지 2번~3번 과정 반복. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과입니다!

 

진입 차수란??

자신을 가리키는 애들(?)의 개수를 말합니다! 위의 문제에서 4번 건물을 예로 든다면 4번 건물의 진입 차수는 2입니다!

왜냐 2번 3번 건물을 짓고나서야 4번 건물을 지을 수 있기 때문이죠 ( 즉 2 번 3번이 4번은 가리키고 있습니다여)

 

자 이제 코드로 보실게여

 

package boj.topologysort

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

private lateinit var arr: ArrayList<ArrayList<Int>>
private lateinit var indegree: IntArray // 진입 차수
private val v1 = intArrayOf(1, 1, 2, 4, 3, 3, 5, 2, 5)
private val v2 = intArrayOf(2, 3, 5, 6, 4, 7, 6, 4, 4)

private var n = 7 // 정점 개수
private var e = 9 // 간선 개수
private fun main() {

    indegree = IntArray(n + 1)
    arr = ArrayList()

    for (i in 0..n) arr.add(ArrayList())

    /**
     * 1. v1 -> v2 인접리스트 생성
     * 2. v2 를 가리키는 노드 갯수 indegree 증가
     */
    for (i in 0 until e) {
        arr[v1[i]].add(v2[i])
        indegree[v2[i]]++
    }

    topologicalSort();
}

private fun topologicalSort() {

    val queue: Queue<Int> = LinkedList()
    val result: Queue<Int> = LinkedList()

    // 진입 차수가 0이면 큐에 추가
    for (i in 1..n) {
        if (indegree[i]==0) queue.offer(i)
    }

    while (queue.isNotEmpty()) {
        val node = queue.poll()
        result.offer(node);

        for (i in arr[node]){
            indegree[i]--
            if (indegree[i]==0){
                queue.offer(i)
            }
        }
    }

    System.out.println(result);
}