스위프트 코딩테스트 강좌, 최단 경로 구하기

여러분 안녕하세요! 오늘은 스위프트로 최단 경로를 구하는 알고리즘 문제를 다뤄보겠습니다. 이 문제는 다양한 알고리즘 면접에서 자주 등장하는 주제 중 하나로, 그래프 이론을 바탕으로 하고 있습니다. 우리는 이 문제를 통해 최단 경로 알고리즘인 Dijkstra 알고리즘에 대해 깊이 있는 이해를 얻고, 이를 스위프트로 구현해볼 것입니다.

문제 설명

주어진 지도 위에 여러 도시와 도로가 있습니다. 각 도시는 번호로 구분되어 있으며, 도로는 두 도시를 연결합니다. 도로에는 각각의 가중치가 있으며, 이는 두 도시 간의 여행 시간이 됩니다. 당신의 목표는 한 도시에서 다른 도시로 가는 최단 경로를 찾는 것입니다.

다음과 같은 형태의 그래프가 주어진다고 가정합니다:

도시의 개수: N (1 ≤ N ≤ 1000)
도로의 개수: M (1 ≤ M ≤ 10000)
각 도로는 두 도시를 연결하며, 그 사이의 가중치가 주어집니다.

당신은 시작 도시와 도착 도시의 번호가 제공되며, 가장 짧은 경로의 가중치 값을 출력해야 합니다.

입력 예시

출력 예시

(경로: 1 → 2 → 5 → 6)

문제 해결 전략

이 문제는 그래프의 최단 경로를 찾는 문제로, Dijkstra 알고리즘을 사용하여 해결할 수 있습니다. Dijkstra 알고리즘은 다음과 같은 단계를 따릅니다.

우선순위 큐를 사용하여 저장된 경로의 가중치를 기준으로 최소 거리를 유지합니다.
시작 노드에서 모든 인접 노드로의 경로 가중치를 업데이트합니다.
최소 가중치를 갖는 도시를 선택하고, 그 도시와 인접한 노드들의 경로 가중치를 업데이트하는 과정을 반복합니다.
목표 도시에 도달하면, 그 가중치를 출력합니다.

스위프트 코드 구현

    import Foundation

    struct Edge {
        let target: Int
        let weight: Int
    }

    func dijkstra(start: Int, end: Int, graph: [[Edge]], n: Int) -> Int {
        var distances = Array(repeating: Int.max, count: n + 1)
        var priorityQueue: [(Int, Int)] = [] // (distance, city)
        distances[start] = 0
        priorityQueue.append((0, start))

        while !priorityQueue.isEmpty {
            priorityQueue.sort(by: { $0.0 < $1.0 }) // 우선순위 큐 정렬
            let (currentDistance, currentCity) = priorityQueue.removeFirst()

            if currentCity == end {
                return currentDistance
            }

            if currentDistance > distances[currentCity] {
                continue
            }

            for edge in graph[currentCity] {
                let newDistance = currentDistance + edge.weight

                if newDistance < distances[edge.target] {
                    distances[edge.target] = newDistance
                    priorityQueue.append((newDistance, edge.target))
                }
            }
        }
        return -1
    }

    func main() {
        let input = """
        6 9
        1 2 2
        1 3 5
        2 3 1
        2 4 5
        3 5 2
        4 6 3
        2 5 3
        1 4 9
        5 6 1
        1 6
        """
        
        var lines = input.components(separatedBy: "\n").filter { !$0.isEmpty }
        let firstLine = lines.removeFirst().split(separator: " ")
        let n = Int(firstLine[0])!
        let m = Int(firstLine[1])!

        var graph = Array(repeating: [Edge](), count: n + 1)

        for line in lines.prefix(m) {
            let parts = line.split(separator: " ")
            let u = Int(parts[0])!
            let v = Int(parts[1])!
            let w = Int(parts[2])!
            graph[u].append(Edge(target: v, weight: w))
            graph[v].append(Edge(target: u, weight: w)) // 무방향 그래프
        }

        let lastLine = lines.last!.split(separator: " ")
        let start = Int(lastLine[0])!
        let end = Int(lastLine[1])!

        let result = dijkstra(start: start, end: end, graph: graph, n: n)
        print(result)
    }

    main()

설명 및 코드 분석

이 코드에서는 우선 그래프를 읽어들이고, 각 도시 간의 간선을 구성하기 위해 `Edge` 구조체를 정의합니다. Dijkstra 알고리즘을 구현하기 위해 `dijkstra` 함수를 정의하고, 필요한 변수와 우선순위 큐를 초기화합니다. 이후에는 현재 도시에서 모든 인접 도시로의 경로 가중치를 계산하고, 이를 반복적으로 진행하여 최단 경로를 찾습니다.

스위프트의 배열과 기본적인 자료 구조를 활용하여 효율적인 최단 경로 구하기 구현이 가능합니다. 각 도시에 대한 거리를 초기화하고, 우선순위 큐를 통해 최소 경로를 업데이트하는 방식이 핵심적입니다.

결론

오늘 강좌에서는 스위프트를 이용해 최단 경로 문제를 해결하는 방법을 배웠습니다. 그래프 이론의 많은 문제들이 기본적으로는 비슷한 접근 방식을 자주 사용하므로, 이번 문제를 통해 Dijkstra 알고리즘을 익혔다면 다른 문제들에도 응용할 수 있습니다.

면접이나 코딩테스트에서 자주 등장하는 주제이니, 반드시 익혀두시길 바랍니다. 다음 시간에는 다른 알고리즘 주제를 다루겠습니다!