라이브스마트

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

플로이드-워셜 알고리즘(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()
    }
}
        

소개

안녕하세요, 이번 코틀린 코딩테스트 강좌에서는 ‘특정 거리의 도시 찾기’라는 알고리즘 문제를 다룹니다.
이 문제는 그래프 탐색 문제로, 주어진 조건에 따라 특정 거리의 도시에 있는 노드들을 찾는 알고리즘적 접근을 요구합니다.
코틀린을 사용하여 문제를 해결하는 방법을 단계별로 살펴보겠습니다.

문제 설명

주어진 그래프는 N개의 도시와 M개의 양방향 도로로 구성되어 있습니다.
각 도시는 1부터 N까지의 번호로 식별되며, 도로는 두 도시 사이에 연결되어 있습니다.
문제를 통해 주어진 거리 K를 갖는 모든 도시를 찾는 것이 목표입니다.

입력 형식
첫 번째 줄에는 도시의 개수 N (1 ≤ N ≤ 30000)과 도로의 개수 M (1 ≤ M ≤ 200000), 찾고자 하는 거리 K (0 ≤ K ≤ 30000)가 주어집니다.
두 번째 줄부터 M개의 줄에는 각각 연결된 두 도시 A, B (1 ≤ A, B ≤ N)의 정보가 주어집니다.

출력 형식
거리 K에 정확히 해당하는 도시의 번호를 오름차순으로 출력하되, 만약 그런 도시가 없다면 -1을 출력합니다.

문제 해결 접근법

이 문제는 그래프에서 주어진 조건에 맞는 정점을 탐색하는 문제입니다.
BFS(너비 우선 탐색) 알고리즘을 사용하여 적절한 깊이까지 탐색함으로써 특정 거리의 도시를 찾을 수 있습니다.
BFS는 비어 있는 큐와 인접 리스트를 이용하여 구현할 수 있습니다.

구현 방법

먼저 주어진 도시와 도로 정보를 기반으로 인접 리스트를 구성합니다.
그 후 BFS 알고리즘을 사용하여 주어진 거리 K에 도달하는 도시를 찾습니다.

구현 순서는 다음과 같습니다:

1. 입력 값 처리: 도시의 개수, 도로의 개수, 거리 K를 읽어옵니다.
2. 인접 리스트 구성: 각 도시와 연결된 다른 도시를 리스트 형태로 저장합니다.
3. BFS 초기화: 시작 도시에서부터 K의 거리를 탐색합니다.
4. 결과 저장: K 거리에 도달한 도시 번호를 리스트에 저장합니다.
5. 결과 출력: K 시점에서 도달한 도시들을 정렬하여 출력합니다.

코드 구현

아래는 코틀린으로 구현한 BFS 알고리즘을 통한 해결 코드입니다:

import java.util.*

fun main() {
    val scanner = Scanner(System.`in`)
    val n = scanner.nextInt() // 도시의 개수
    val m = scanner.nextInt() // 도로의 개수
    val k = scanner.nextInt() // 찾고자 하는 거리
    val x = scanner.nextInt() // 출발 도시

    // 인접 리스트 초기화
    val graph = Array(n + 1) { mutableListOf() }

    // 도로 정보 입력 받기
    for (i in 0 until m) {
        val a = scanner.nextInt()
        val b = scanner.nextInt()
        graph[a].add(b)
        graph[b].add(a)
    }

    // BFS 구현
    val distance = IntArray(n + 1) { -1 }
    distance[x] = 0
    val queue: Queue = LinkedList()
    queue.add(x)

    while (queue.isNotEmpty()) {
        val current = queue.poll()
        for (neighbor in graph[current]) {
            if (distance[neighbor] == -1) {
                distance[neighbor] = distance[current] + 1
                queue.add(neighbor)
            }
        }
    }

    // 결과 도시 찾기
    val result = mutableListOf()
    for (i in 1..n) {
        if (distance[i] == k) {
            result.add(i)
        }
    }

    // 결과 출력
    if (result.isEmpty()) {
        println(-1)
    } else {
        result.sort()
        for (city in result) {
            println(city)
        }
    }
}
        

해설

위의 코드는 주어진 문제를 해결하기 위한 전형적인 BFS 구현 방식입니다.
특히 도로의 연결 상태를 인접 리스트로 표현하여 메모리 사용을 최적화하고, 빠른 탐색을 가능하게 합니다.
BFS는 모든 노드를 탐색하며, 노드와 연결된 인접 노드를 큐에 넣는 방식으로 작동합니다.
이렇게 하여 각 노드까지의 거리를 갱신하며 최종적으로 거리 K에서 멈춘 노드들을 수집합니다.

만약 거리가 K인 도시가 없을 경우, -1을 출력하며 결과를 처리하는 것도 좋은 프로그래밍 습관입니다.
이 코드 구조는 문제 유형에 맞춰 쉽게 수정할 수 있어 다양한 그래프 탐색 문제에 적용 가능합니다.

결론

이상으로 ‘특정 거리의 도시 찾기’ 문제를 비롯해 BFS 알고리즘을 활용한 코틀린 코드 구현 과정에 대해 알아보았습니다.
이 문제는 그래프 문제의 기초를 이해하는 데 도움을 주며, 다양한 문제 유형에 대한 문제 해결 능력을 키울 수 있습니다.
업무나 개인 프로젝트에서 알고리즘을 효율적으로 적용하는 데에도 많은 도움을 줄 것입니다.
추후 더 다양한 알고리즘 문제들도 다룰 예정이니 많은 관심 부탁드립니다.