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

오늘은 스위프트를 이용하여 코딩 테스트를 준비하는 여러분을 위해 ‘가장 빠른 버스 노선 구하기’라는 문제를
다뤄보겠습니다. 이 문제는 그래프 탐색 특히 최단 경로 알고리즘에 대한 이해를 요구합니다. 실제
코딩 테스트에서 자주 출제되는 유형의 문제이므로 주의 깊게 살펴보시기를 바랍니다.

문제 설명

당신은 한 도시의 버스 노선 정보를 가지고 있습니다. 이 도시에는 N개의 정거장이 있고, 정거장 i와 j
사이를 잇는 버스 노선이 존재합니다. 각 노선에는 이동 시간, 즉 가중치가 부여되어 있습니다.
당신의 목표는 특정 정거장 S에서 출발하여 정거장 E에 도착하는 가장 빠른 경로를 찾는 것입니다.
만약 경로가 존재하지 않을 경우 “도착할 수 없습니다”라고 출력해야 합니다.

입력 형식

첫 번째 줄에는 정거장의 수 N(1 ≤ N ≤ 1000)과 버스 노선의 수 M(1 ≤ M ≤ 1000)이 주어집니다.
다음 M개의 줄에는 정거장 i, j, 해당 버스 노선의 이동 시간 T가 주어집니다.
마지막으로 두 개의 정거장 S와 E가 주어집니다.

출력 형식

가장 빠른 이동 시간 또는 “도착할 수 없습니다”를 출력해주세요.

예제 입력

예제 출력

문제 풀이 과정

이 문제를 해결하기 위해 최단 경로 알고리즘 중 하나인 다익스트라 알고리즘을 사용합니다.
다익스트라 알고리즘은 가중치가 있는 그래프에서 최단 경로를 찾는 데 유용합니다.

알고리즘 개요

다익스트라 알고리즘은 우선순위 큐를 사용하여 다음 정점을 선택하고, 그 정점과 연결된
모든 정점으로 가는 경로를 업데이트하는 방식으로 작동합니다. 그래프의 모든 정점에 대해 초기화와
업데이트 과정을 거치면서 최단 거리를 점차 확장해 나갑니다.

구현 단계

입력값 받기: 정거장 수 N, 노선 수 M을 입력 받습니다. 이어서 M개의 노선 정보를
받습니다.
그래프 구조 만들기: 인접 리스트 형태로 그래프를 저장합니다.
다익스트라 알고리즘 구현: 시작 정거장에서 모든 정거장으로 가는
최단 경로를 계산합니다.
결과 출력: 도착 지점의 최단 시간 또는 “도착할 수 없습니다”를 출력합니다.

스위프트 코드 구현

    import Foundation

    struct BusRoute {
        let destination: Int
        let time: Int
    }

    func dijkstra(n: Int, graph: [[BusRoute]], start: Int, end: Int) -> Int {
        var distances = Array(repeating: Int.max, count: n + 1)
        var priorityQueue = [(Int, Int)]()  // (정거장, 시간)
        distances[start] = 0
        priorityQueue.append((start, 0))
        
        while !priorityQueue.isEmpty {
            priorityQueue.sort { $0.1 < $1.1 }
            let (current, currentDistance) = priorityQueue.removeFirst()

            if currentDistance > distances[current] {
                continue
            }

            for route in graph[current] {
                let newDistance = currentDistance + route.time
                if newDistance < distances[route.destination] {
                    distances[route.destination] = newDistance
                    priorityQueue.append((route.destination, newDistance))
                }
            }
        }

        return distances[end] == Int.max ? -1 : distances[end]
    }

    func main() {
        let input = readLine()!.split(separator: " ").map { Int($0)! }
        let n = input[0]
        let m = input[1]
        var graph = Array(repeating: [BusRoute](), count: n + 1)

        for _ in 0..

    코드 설명
    
        위 코드는 다익스트라 알고리즘을 구현한 것입니다. 입력을 통해 그래프를 구성한 뒤, 주어진 
        시작점에서 최단 경로를 계산하고 결과를 출력합니다. 우선순위 큐를 사용하여 가장 빠른 경로를 
        찾는 것이 핵심입니다. 
    

    결론
    
        이번 문제를 통해 코딩 테스트에서 자주 출제되는 최단 경로 문제에 대한 이해를 높였길 바랍니다. 
        다익스트라 알고리즘뿐 아니라 다양한 그래프 알고리즘을 활용하여 여러 문제를 해결할 수 있습니다. 
        지속적인 연습을 통해 이론과 실력을 모두 갖춘 개발자가 되기를 응원합니다.

관련