코틀린 코딩테스트 강좌, 벨만-포드

1. 서론

코딩 테스트는 현대의 기술 직군에서 필수적인 능력을 평가하는 중요한 단계입니다. 특히 그래프 이론은 알고리즘 문제에서 흔히 요구되는 주제이며, 그중에서도 벨만-포드 알고리즘은 단일 출발점에서 최단 경로를 찾는 문제를 해결하는 데 널리 사용됩니다. 이번 글에서는 코틀린을 사용하여 벨만-포드 알고리즘을 구현하고, 문제를 해결하는 과정을 자세히 설명하겠습니다.

2. 벨만-포드 알고리즘 소개

벨만-포드 알고리즘은 주어진 그래프에서 하나의 정점에서 다른 모든 정점으로의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 특히 음의 가중치를 가진 간선이 존재할 때 유용합니다. 벨만-포드 알고리즘은 다음과 같은 단계로 작동합니다:

시작 정점의 거리 값을 0으로 초기화하고, 나머지 정점의 거리 값을 무한대로 설정합니다.
그래프의 모든 간선을 |V| – 1번 반복하여, 각 간선(u, v)에 대해 distance[v] = min(distance[v], distance[u] + weight(u, v))을 수행합니다.
마지막으로, 음의 가중치 사이클이 있는지 확인하기 위해 모든 간선을 한 번 더 검사합니다.

3. 문제 설명

문제: 최단 경로 찾기

다음과 같은 그래프가 있다. 정점과 간선은 아래와 같이 주어졌다. 각 간선의 가중치는 표시되어 있다.

        정점:
        0, 1, 2, 3, 4

        간선:
        0 -> 1 (4)
        0 -> 2 (1)
        1 -> 2 (2)
        1 -> 3 (5)
        2 -> 3 (8)
        3 -> 4 (3)
        2 -> 4 (7)

0번 정점에서 다른 모든 정점으로의 최단 경로를 계산하라.

4. 문제 풀이 과정

4.1 입력 데이터 설계

먼저, 위의 그래프를 코드로 표현하기 위해, 정점과 간선을 데이터 구조로 정의해야 합니다. 코틀린에서는 리스트와 데이터 클래스를 사용하여 쉽게 구현할 수 있습니다.

4.2 코틀린 데이터 클래스 정의

        data class Edge(val u: Int, val v: Int, val weight: Int)

4.3 벨만-포드 알고리즘 구현

        fun bellmanFord(edges: List, vertexCount: Int, startVertex: Int): IntArray {
            val distance = IntArray(vertexCount) { Int.MAX_VALUE }
            distance[startVertex] = 0

            for (i in 1 until vertexCount) {
                for (edge in edges) {
                    if (distance[edge.u] != Int.MAX_VALUE && distance[edge.u] + edge.weight < distance[edge.v]) {
                        distance[edge.v] = distance[edge.u] + edge.weight
                    }
                }
            }

            // 음의 가중치 사이클 검증
            for (edge in edges) {
                if (distance[edge.u] != Int.MAX_VALUE && distance[edge.u] + edge.weight < distance[edge.v]) {
                    throw IllegalArgumentException("음의 가중치 사이클 존재")
                }
            }

            return distance
        }

5. 전체 구현

        fun main() {
            val edges = listOf(
                Edge(0, 1, 4),
                Edge(0, 2, 1),
                Edge(1, 2, 2),
                Edge(1, 3, 5),
                Edge(2, 3, 8),
                Edge(3, 4, 3),
                Edge(2, 4, 7)
            )
            
            val result = bellmanFord(edges, 5, 0)
            println("0번 정점에서 다른 정점까지의 최단 거리: ${result.joinToString(", ")}")
        }

6. 출력 결과

위 코드를 실행하면 0번 정점에서 다른 모든 정점까지의 최단 거리를 알 수 있습니다. 기대하는 결과는 다음과 같습니다:

        0번 정점에서 다른 정점까지의 최단 거리: 0, 3, 1, 11, 10

7. 결론

벨만-포드 알고리즘을 사용하여 최단 경로 문제를 해결하는 과정을 살펴보았습니다. 이 알고리즘은 단순하면서도 강력한 기능을 제공합니다. 특히 음의 가중치가 있을 때 유용하게 사용될 수 있음을 강조하고 싶습니다. 코틀린을 이용해 구현해보면서, 알고리즘의 작동 방식을 더욱 잘 이해할 수 있었을 것입니다. 코딩 테스트를 준비하며 벨만-포드 알고리즘을 실습해보세요!