코틀린 코딩테스트 강좌, 최소 비용 구하기

안녕하세요! 이번 포스팅에서는 코틀린으로 해결할 수 있는 알고리즘 문제를 다루어 보겠습니다.
주제는 최소 비용 구하기입니다. 이 문제는 다양한 형태로 출제될 수 있으며, 코딩 테스트에서 자주 접하는 유형입니다.
이 글에서는 문제 설명, 알고리즘 설계, 코틀린 코드 구현, 예제 및 테스트 케이스를 포함한 체계적인 문제 해결 과정을 설명하겠습니다.

문제 설명

N개의 정점과 M개의 간선이 연결된 방향 그래프가 있습니다. 각 간선은 비가역적이며, 특정 비용이 부여되어 있습니다.
여러분의 임무는 특정 시작 정점에서 목표 정점까지의 최소 비용을 구하는 것입니다.
간선들은 다양하게 연결되어 있을 수 있으며, 같은 정점으로 가는 여려 경로가 있을 수 있습니다.

입력 형식:

  • 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다.
  • 둘째 줄부터 M줄에 걸쳐 간선 정보: 시작 정점 A, 도착 정점 B, 비용 C가 주어진다.
  • 마지막 줄에는 시작 정점과 목표 정점이 주어진다.

출력 형식:

  • 시작 정점에서 목표 정점까지 도달하는 최소 비용을 출력한다. 만약 도달할 수 없다면 -1을 출력한다.

예시 입력

5 6
1 2 2
1 3 3
2 4 1
3 4 4
2 5 5
4 5 1
1 5

예시 출력

8

문제 해결 접근법

이 문제는 최단 경로 문제로, Dijkstra 알고리즘을 사용하여 효과적으로 해결할 수 있습니다. Dijkstra 알고리즘은
그래프에서 특정 출발 정점으로부터 다른 모든 정점까지의 최단 경로를 구하는 데 탁월한 성능을 보입니다.
본 장에서는 Dijkstra 알고리즘의 개요와 코틀린으로 구현하는 방법에 대해 자세히 살펴보겠습니다.

Dijkstra 알고리즘 개요

Dijkstra 알고리즘은 다음과 같은 원리에 기반하여 작동합니다:

  • 시작 정점에서 다른 모든 정점까지의 최단 경로를 초기화합니다. 시작 정점으로부터의 거리는 0으로 설정하고, 나머지 정점은 무한대로 설정합니다.
  • 우선순위 큐를 사용하여 현재까지 발견된 최단 거리 중 가장 짧은 경로를 가진 정점을 반복적으로 선택합니다.
  • 선택된 정점의 인접 정점에 대해 최단 거리 기준으로 거리를 갱신합니다.
  • 모든 정점이 선택되거나, 남은 정점 모두의 거리가 무한대일 때까지 이 과정을 반복합니다.

이 과정을 통해 최종적으로 시작 정점에서 목표 정점까지의 최소 비용을 찾을 수 있습니다.

코틀린 코드 구현

이제 문제를 해결하기 위해 Dijkstra 알고리즘을 코틀린으로 구현해 보겠습니다.
먼저 필요한 라이브러리를 가져오고 입력을 처리한 후, 알고리즘을 구현하는 구조로 진행합니다. 


import java.util.PriorityQueue

data class Edge(val to: Int, val cost: Int)

fun dijkstra(n: Int, edges: List>, start: Int): IntArray {
    val distance = IntArray(n + 1) { Int.MAX_VALUE }
    val priorityQueue = PriorityQueue>(compareBy { it.first })
    
    distance[start] = 0
    priorityQueue.add(0 to start)

    while (priorityQueue.isNotEmpty()) {
        val (currentDist, currentNode) = priorityQueue.poll()
        
        if (currentDist > distance[currentNode]) continue

        for (edge in edges[currentNode]) {
            val newDist = currentDist + edge.cost
            
            if (newDist < distance[edge.to]) {
                distance[edge.to] = newDist
                priorityQueue.add(newDist to edge.to)
            }
        }
    }

    return distance
}

fun main() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val edges = List(n + 1) { mutableListOf() }

    for (i in 1..m) {
        val (a, b, cost) = readLine()!!.split(" ").map { it.toInt() }
        edges[a].add(Edge(b, cost))
    }

    val (start, end) = readLine()!!.split(" ").map { it.toInt() }
    val distances = dijkstra(n, edges, start)

    println(if (distances[end] == Int.MAX_VALUE) -1 else distances[end])
}

코드 설명

위의 코드는 Dijkstra 알고리즘을 사용하여 문제를 해결하는 코틀린 프로그램입니다. 코드의 주요 구성 요소를 살펴보겠습니다.

  • Edge 데이터 클래스: 그래프의 간선을 표현하는 데이터 클래스입니다. 각 간선은 도착 정점과 비용 정보를 갖습니다.
  • dijkstra 함수: Dijkstra 알고리즘을 구현한 함수입니다. 입력으로 정점 수 n, 간선 리스트 edges, 시작 정점 start를 받아들입니다.
    최단 경로 정보를 저장할 distance 배열을 초기화하고, 우선순위 큐를 사용하여 경로를 탐색합니다.
  • main 함수: 입력을 처리하고 dijkstra 기능을 호출합니다. 최종적으로 목표 정점까지의 최소 비용을 출력합니다.
    만약 도달할 수 없는 경우에는 -1을 출력합니다.

테스트 케이스

코드의 기능을 확인하기 위해 몇 가지 테스트 케이스를 작성해 보겠습니다.
다양한 상황을 고려하여 코드의 성능과 정확성을 확인하는 것이 중요합니다.

테스트 케이스 1


입력:
5 6
1 2 2
1 3 3
2 4 1
3 4 4
2 5 5
4 5 1
1 5

출력:
8

테스트 케이스 2


입력:
3 2
1 2 2
1 3 4
2 3 5
1 3

출력:
4

테스트 케이스 3


입력:
4 3
1 2 10
2 3 5
3 4 10
1 4

출력:
-1

결론

이번 포스팅에서는 코틀린을 사용하여 최소 비용 구하기 문제를 해결하는 방법에 대해 알아보았습니다.
Dijkstra 알고리즘을 이용하여 그래프의 최단 경로를 효율적으로 찾아내는 방법을 설명하였고,
이를 코틀린으로 구현하였으며, 여러 테스트 케이스를 통해 코드의 작동을 확인했습니다.
알고리즘과 코틀린 프로그래밍에 대한 이해를 깊이 있게 다룰 수 있었던 시간이었습니다.
다음에도 유용한 알고리즘 문제와 솔루션으로 돌아오겠습니다.
감사합니다!