코틀린 코딩테스트 강좌, 최단 경로 구하기

문제 설명

특정한 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 문제는 그래프 이론에서 매우 중요한 문제입니다.
이 문제를 해결하기 위해서는 다양한 알고리즘을 사용할 수 있으며, 대표적으로 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-워셜 알고리즘 등이 있습니다.

이번 강좌에서는 다익스트라 알고리즘을 중심으로 최단 경로를 구하는 문제를 다루겠습니다.
문제의 구체적인 형태는 다음과 같습니다.

주어진 간선들을 가지고 방향그래프를 구성한 후, 시작 정점에서 다른 모든 정점까지의 최단 경로를 구하여라.
입력으로는 정점의 개수 N, 간선의 개수 M이 주어지고,
각 간선은 시작 정점 A, 도착 정점 B, 가중치 C로 이루어진다.

문제 예시

입력 예시:

출력 예시:

여기서 첫 번째 줄은 정점의 개수(N)와 간선의 개수(M)를 나타내며,
그 다음 줄부터는 각 간선의 정보를 나타냅니다.
시작 정점은 1로 하며, 0은 자기 자신으로의 최단 경로를 의미합니다.

문제 해결 과정

1. 다익스트라 알고리즘 개요

다익스트라 알고리즘은 그래프에서 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다.
이 알고리즘은 음의 가중치를 가지지 않는 그래프에서 유효하며, 일반적으로 우선순위 큐를 이용하여 구현됩니다.

이 알고리즘의 기본 아이디어는 매 단계에서 현재까지 구한 최단 경로를 기반으로,
아직 최단 경로가 계산되지 않은 정점들 사이의 경로를 업데이트하는 것입니다.

2. 알고리즘 단계

시작 정점에서 모든 정점까지의 거리를 무한대로 초기화합니다. 단, 시작 정점의 거리는 0으로 초기화합니다.
우선순위 큐를 사용하여 현재 가장 가까운 정점을 선택합니다.
선택된 정점의 거리를 사용하여 인접 정점의 거리 값을 업데이트합니다.
모든 정점의 거리가 확정될 때까지 2~3번 단계를 반복합니다.

3. 코틀린 코드 구현

이제 이러한 과정을 코틀린으로 구현해 보겠습니다. 아래는 다익스트라 알고리즘을 사용하여 주어진 문제를 해결하는 코드입니다.

                
                    import java.util.PriorityQueue
                    import kotlin.math.min

                    data class Edge(val target: Int, val weight: Int)

                    fun dijkstra(n: Int, edges: List>, start: Int): IntArray {
                        val graph = MutableList(n + 1) { mutableListOf() }
                        for ((a, b, c) in edges) {
                            graph[a].add(Edge(b, c))
                        }

                        val distances = IntArray(n + 1) { Int.MAX_VALUE }
                        distances[start] = 0

                        val priorityQueue = PriorityQueue>(compareBy { it.first })
                        priorityQueue.add(0 to start)

                        while (priorityQueue.isNotEmpty()) {
                            val (dist, current) = priorityQueue.poll()

                            if (dist > distances[current]) continue

                            for (edge in graph[current]) {
                                val newDist = dist + edge.weight
                                if (newDist < distances[edge.target]) {
                                    distances[edge.target] = newDist
                                    priorityQueue.add(newDist to edge.target)
                                }
                            }
                        }

                        return distances
                    }

                    fun main() {
                        val input = readLine()!!.split(" ").map { it.toInt() }
                        val n = input[0]
                        val m = input[1]

                        val edges = mutableListOf>()
                        for (i in 0 until m) {
                            val edgeInput = readLine()!!.split(" ").map { it.toInt() }
                            edges.add(Triple(edgeInput[0], edgeInput[1], edgeInput[2]))
                        }

                        val distances = dijkstra(n, edges, 1)

                        for (i in 1..n) {
                            println(if (distances[i] == Int.MAX_VALUE) "INF" else distances[i])
                        }
                    }

위의 코드에서 dijkstra 함수는 정점의 개수와 간선 정보를 입력받아 시작 정점으로부터의 최단 경로를 계산합니다.
distances 배열은 각 정점까지의 최단 경로 거리를 저장하며, 초기에는 무한대로 설정됩니다.

주어진 입력을 처리한 후, 메인 함수는 distances 배열을 출력합니다.
만약 도달할 수 없는 정점이 있다면 “INF”로 표시하였습니다.

테스트 및 검증

알고리즘을 구현한 후에는 다양한 테스트 케이스를 통해 코드의 정확성을 검증해야 합니다.
예를 들어, 다음과 같은 추가 테스트 케이스를 고려해보세요:

연산 결과는 다음과 같아야 합니다:

실제 입력을 주고 코드의 출력을 비교하여 정확성을 확인하세요.
다양한 상황을 고려하여 엣지 케이스를 처리하는 것 역시 중요합니다.

결론

이번 강좌에서는 다익스트라 알고리즘을 통해 최단 경로 구하기 문제를 다뤄보았습니다.
코틀린을 사용하여 알고리즘을 구현하며, 이론적인 배경과 실제 구현을 연결하는 과정을 지나쳤습니다.
코딩 테스트를 준비하며 다양한 알고리즘과 자료구조를 익혀, 자신만의 문제 해결 능력을 키워 보시기 바랍니다.