[kotlin] 코틀린으로 위상 정렬 알고리즘 작성하기

14 Dec 2023

kotlin

코틀린을 사용하여 위상 정렬 알고리즘을 작성하려면 해당 그래프의 각 노드에 대한 인접 리스트를 만들어야 합니다. 그 다음, 각 노드의 진입 차수를 계산하고, 진입 차수가 0인 모든 노드를 큐에 넣어야 합니다. 반복적으로 큐에서 노드를 추출하고 해당 노드에서 출발하는 간선을 제거한 뒤, 도착 노드의 진입 차수를 업데이트해야 합니다.

다음은 코틀린으로 위상 정렬 알고리즘을 작성하는 예제 코드입니다.

class TopologicalSort(val graph: Map<Int, List<Int>>) {
    private val inDegree = mutableMapOf<Int, Int>()

    init {
        graph.keys.forEach { node ->
            inDegree[node] = 0
        }
        graph.values.forEach { adjacentNodes ->
            adjacentNodes.forEach { adjNode ->
                inDegree[adjNode] = inDegree.getOrDefault(adjNode, 0) + 1
            }
        }
    }

    fun sort(): List<Int> {
        val queue = ArrayDeque<Int>()
        val result = mutableListOf<Int>()
        inDegree.filter { it.value == 0 }.keys.forEach { queue.addLast(it) }

        while (queue.isNotEmpty()) {
            val node = queue.removeFirst()
            result.add(node)
            graph[node]?.forEach { adjNode ->
                inDegree[adjNode] = inDegree.getValue(adjNode) - 1
                if (inDegree.getValue(adjNode) == 0) {
                    queue.addLast(adjNode)
                }
            }
        }

        return if (result.size == graph.size) {
            result
        } else {
            emptyList()
        }
    }
}

fun main() {
    val graph = mapOf(
        1 to listOf(2, 3),
        2 to listOf(4),
        3 to listOf(4),
        4 to emptyList()
    )
    val topologicalSort = TopologicalSort(graph)
    val result = topologicalSort.sort()
    if (result.isNotEmpty()) {
        println("Topological order: $result")
    } else {
        println("Graph has a cycle!")
    }
}

이 코드에서는 TopologicalSort 클래스를 사용하여 주어진 그래프의 위상 정렬을 수행합니다. sort 메서드를 호출하여 해당 그래프의 위상 순서를 확인할 수 있습니다.

이제 위상 정렬 알고리즘을 사용하여 주어진 코틀린 그래프를 나열하는 방법을 이해했습니다.