코틀린 코딩테스트 강좌, 가장 빠른 버스 노선 구하기

코틀린을 활용한 코딩테스트 강좌의 일환으로, 가장 빠른 버스 노선을 구하는 문제를 다뤄보겠습니다. 현대 사회에서 대중교통은 중요한 이동 수단이며, 특히 버스를 이용한 이동 경로 파악은 많은 사람들이 필요로 하는 기능입니다. 본 문제에서는 주어진 조건에 따라 최단 시간을 계산하는 알고리즘을 설계하고 구현해볼 것입니다.

문제 정의

다음과 같이 여러 개의 버스 노선이 주어집니다. 각 노선은 시작 정류장, 도착 정류장, 소요 시간을 포함합니다. 여러분의 목표는 특정 시작 정류장에서 특정 도착 정류장까지의 가장 빠른 소요 시간을 구하는 것입니다.

문제 입력

- 정류장의 수 N (1 ≤ N ≤ 100)
- 노선의 수 M (1 ≤ M ≤ 1000)
- 각 노선 정보: 시작 정류장 A, 도착 정류장 B, 소요 시간 T (1 ≤ A, B ≤ N, 1 ≤ T ≤ 1000)
- 시작 정류장 S와 도착 정류장 D

문제 출력

- 시작 정류장에서 도착 정류장까지 가는 가장 빠른 소요 시간. 불가능한 경우 -1을 출력.

문제 해결 전략

본 문제는 최단 경로를 찾는 문제로, 적합한 알고리즘으로는 Dijkstra의 최단 경로 알고리즘을 사용할 수 있습니다. Dijkstra 알고리즘은 가중치가 있는 그래프에서 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 데 유용합니다. 버스 노선 정보를 그래프로 구축하고, 해당 그래프를 활용하여 최단 시간을 계산할 것입니다.

단계별 접근 방법

1단계: 입력 데이터 구조 정의

우선, 주어진 노선 정보를 바탕으로 그래프를 어떤 형식으로 표현할지를 결정합니다. 인접 리스트를 사용하여 각 정류장과 연결된 노선 정보를 관리하는 것이 효율적입니다.

val graph: Array>> = Array(N + 1) { mutableListOf() }

2단계: 입력 데이터 처리

사용자로부터 입력받은 노선 정보를 그래프 형태로 변환합니다. 각 노선 정보를 알맞은 형식으로 그래프에 추가합니다.

for (i in 0 until M) {
    val (A, B, T) = readLine()!!.split(" ").map { it.toInt() }
    graph[A].add(Pair(B, T))
}

3단계: Dijkstra 알고리즘 구현

Dijkstra 알고리즘을 이용하여 모든 정류장에 대한 최단 경로를 계산합니다. 우선순위 큐를 사용하여 현재 소요 시간이 가장 적은 노선을 먼저 처리합니다.

fun dijkstra(start: Int): IntArray {
    val distances = IntArray(N + 1) { Int.MAX_VALUE }
    distances[start] = 0
    val priorityQueue = PriorityQueue>(compareBy { it.second })
    priorityQueue.add(Pair(start, 0))

    while (priorityQueue.isNotEmpty()) {
        val (currentStation, currentTime) = priorityQueue.poll()

        if (currentTime > distances[currentStation]) continue

        for (edge in graph[currentStation]) {
            val (nextStation, travelTime) = edge
            val newTime = currentTime + travelTime

            if (newTime < distances[nextStation]) {
                distances[nextStation] = newTime
                priorityQueue.add(Pair(nextStation, newTime))
            }
        }
    }
    return distances
}

4단계: 결과 출력

최종적으로 시작 정류장에서 도착 정류장까지의 최단 소요 시간을 출력합니다. 만약 도착 정류장에 도달할 수 없는 경우 -1을 출력합니다.

val distances = dijkstra(S)
println(if (distances[D] == Int.MAX_VALUE) -1 else distances[D])

전체 코드 예제

fun main() {
    val (N, M) = readLine()!!.split(" ").map { it.toInt() }
    val graph: Array>> = Array(N + 1) { mutableListOf() }

    for (i in 0 until M) {
        val (A, B, T) = readLine()!!.split(" ").map { it.toInt() }
        graph[A].add(Pair(B, T))
    }

    val (S, D) = readLine()!!.split(" ").map { it.toInt() }
    val distances = dijkstra(S)

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

fun dijkstra(start: Int): IntArray {
    val distances = IntArray(N + 1) { Int.MAX_VALUE }
    distances[start] = 0
    val priorityQueue = PriorityQueue>(compareBy { it.second })
    priorityQueue.add(Pair(start, 0))

    while (priorityQueue.isNotEmpty()) {
        val (currentStation, currentTime) = priorityQueue.poll()

        if (currentTime > distances[currentStation]) continue

        for (edge in graph[currentStation]) {
            val (nextStation, travelTime) = edge
            val newTime = currentTime + travelTime

            if (newTime < distances[nextStation]) {
                distances[nextStation] = newTime
                priorityQueue.add(Pair(nextStation, newTime))
            }
        }
    }
    return distances
}

결론

이번 강좌에서는 코틀린을 사용하여 가장 빠른 버스 노선을 선택하는 문제를 해결해 보았습니다. Dijkstra 알고리즘을 통해 최단 경로 문제를 해결하는 과정과, 문제의 여러 요소를 고려하여 코드로 구현하는 방법을 배울 수 있었습니다. 알고리즘 문제는 연습을 통해 더 나아질 수 있으므로, 지속적으로 다양한 문제를 풀어보는 것을 추천합니다.