코틀린 코딩테스트 강좌, 플로이드-워셜

알고리즘 문제 풀이 및 이론 설명

플로이드-워셜 알고리즘 소개

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프 내 모든 정점 간 최단 경로를 찾는 알고리즘입니다.
이 알고리즘은 주어진 그래프의 모든 쌍의 최단 거리를 계산하는 데 적합하며,
특히 음의 가중치가 있는 경우에도 작동합니다.
그 복잡도는 O(V^3)으로, V는 정점의 수를 의미합니다.
플로이드-워셜 알고리즘은 동적 프로그래밍 기법을 활용하여 최단 경로를 계산하며,
단계적으로 최적해를 구축해 나가는 방식입니다.

문제 설명

주어진 도시들 간의 통행로와 거리가 주어졌을 때,
모든 도시 간의 최단 거리를 구하는 문제를 해결해보겠습니다.
이는 교통량이 많은 도시들에 대한 최적 경로를 찾는 데 매우 유용합니다.

문제

N개의 도시가 있고, 도시들 간의 길이 주어질 때,
모든 도시 간의 최단 거리를 출력하는 프로그램을 작성하시오.
입력 예시는 다음과 같습니다:

3
0 4 2
float(inf) 0 5
float(inf) float(inf) 0

출력 예시는 다음과 같습니다:

0 4 2
float(inf) 0 5
float(inf) float(inf) 0

풀이 과정

1. 입력 처리

문제를 해결하기 위해 입력을 처리합니다.
첫 번째 줄에는 도시의 개수 N이 주어지고, 다음 N줄에는 각 도시 간의 거리 정보를 입력받습니다.
‘float(inf)’는 두 도시 간에 경로가 없음을 나타냅니다.

2. 초기 행렬 생성

주어진 거리 정보를 바탕으로 2차원 배열을 생성하여 초기 행렬을 구성합니다.
이 행렬은 도시 A에서 도시 B로 가는 거리 정보를 가지고 있으며,
초기값은 주어진 거리로 설정하고, 경로가 없는 경우 ‘float(inf)’로 설정합니다.

3. 플로이드-워셜 알고리즘 적용

다음 단계는 플로이드-워셜 알고리즘을 적용하는 것입니다.
알고리즘은 각 도시 K를 중간 정점으로 하여,
도시 I에서 J로 가는 경로가 도시 I에서 K를 거쳐 도시 K에서 J를 지나가는 것이 더 짧은지를 판단하여(즉,
distance[I][J] > distance[I][K] + distance[K][J] 인 경우),
더 짧은 경로로 업데이트합니다.

4. 결과 출력

모든 도시 간의 최단 거리 행렬을 출력합니다.
결과는 각 도시의 최단 거리와 ‘float(inf)’를 구분하여 포맷팅하여 보여줍니다.

5. 코틀린 구현

fun floydWarshall(graph: Array) {
    val n = graph.size
    for (k in 0 until n) {
        for (i in 0 until n) {
            for (j in 0 until n) {
                if (graph[i][j] > graph[i][k] + graph[k][j]) {
                    graph[i][j] = graph[i][k] + graph[k][j]
                }
            }
        }
    }
}

// Main function to execute the program
fun main() {
    val n = readLine()!!.toInt()
    val graph = Array(n) { IntArray(n) { Int.MAX_VALUE } }
    
    // Initialize the graph with input
    for (i in 0 until n) {
        val distances = readLine()!!.split(" ").map { it.toInt() }
        for (j in 0 until n) {
            graph[i][j] = distances[j]
        }
        graph[i][i] = 0 // Distance from a city to itself is always 0
    }
    
    floydWarshall(graph)
    
    // Output the final distance matrix
    for (i in 0 until n) {
        for (j in 0 until n) {
            if (graph[i][j] == Int.MAX_VALUE) {
                print("float(inf) ")
            } else {
                print("${graph[i][j]} ")
            }
        }
        println()
    }
}