스위프트 코딩테스트 강좌, 최소 비용 구하기

문제 설명

주어진 도시에서 시작하여 다른 도시로 가는 비용을 최소화하는 경로를 찾는 문제입니다.
여기서 각 도시는 그래프의 노드로 표현되며 도시는 길로 연결됩니다.
각각의 길에는 이동하는 데 필요한 비용이 각각 다르게 설정되어 있습니다.
목표는 출발 도시에서 도착 도시까지 도달하는 데 최소 비용을 찾는 것입니다.

다음은 문제의 예시입니다:

입력:

도시의 개수 N, 도로의 개수 M

이후 M개의 줄에 각 도로의 정보가 주어집니다.

도로의 정보는 (A, B, C)로서, A 도시에서 B 도시로 가는 데 C의 비용이 필요하다는 뜻입니다.

마지막으로 시작 도시와 도착 도시가 주어집니다.

출력:

시작 도시에서 도착 도시까지의 최소 비용

문제 해결 전략

이 문제를 해결하기 위해 다익스트라 알고리즘을 사용할 것입니다.
다익스트라 알고리즘은 가중치가 있는 그래프에서 최단 경로를 찾기 위한 알고리즘으로,
주로 비관계 비용을 다루는데 효과적입니다.
이 알고리즘의 주요 아이디어는 현재까지의 최단 경로를 기반으로
아직 방문하지 않은 노드 중에서 가장 가까운 노드를 선택하는 것입니다.

다익스트라 알고리즘을 사용하여 단계적으로 문제를 해결하는 방법은 다음과 같습니다:

1. 그래프를 인접 리스트 형태로 구성합니다.
2. 각 도시까지의 최소 비용을 저장할 배열을 초기화합니다.
3. 출발 도시에서 시작하여 인접한 도시에 대한 정보를 업데이트합니다.
4. 우선순위 큐를 사용하여 다음 방문할 도시를 결정합니다.
5. 도착 도시에 도달할 때까지 반복합니다.

스위프트 코드 구현

이제 위의 전략에 따라 스위프트로 코드를 구현해보겠습니다.
다음은 다익스트라 알고리즘을 구현한 예시 코드입니다:

import Foundation

struct Edge {
    let to: Int
    let cost: Int
}

func dijkstra(start: Int, end: Int, graph: [[Edge]]) -> Int {
    var minCosts = Array(repeating: Int.max, count: graph.count)
    var priorityQueue = [(cost: Int, vertex: Int)]()
    minCosts[start] = 0
    priorityQueue.append((0, start))
    
    while !priorityQueue.isEmpty {
        let current = priorityQueue.removeFirst()
        
        if current.vertex == end {
            return current.cost
        }
        
        for edge in graph[current.vertex] {
            let newCost = current.cost + edge.cost
            if newCost < minCosts[edge.to] {
                minCosts[edge.to] = newCost
                priorityQueue.append((newCost, edge.to))
            }
        }
        
        priorityQueue.sort { $0.cost < $1.cost }
    }
    
    return minCosts[end] == Int.max ? -1 : minCosts[end]
}

// 그래프의 예시
let N = 5  // 도시의 개수
let M = 7  // 도로의 개수
var graph = [[Edge]](repeating: [], count: N)

let roads: [(Int, Int, Int)] = [
    (0, 1, 10),
    (0, 2, 5),
    (1, 2, 2),
    (1, 3, 1),
    (2, 1, 3),
    (2, 3, 9),
    (3, 4, 2)
]

for road in roads {
    graph[road.0].append(Edge(to: road.1, cost: road.2))
    graph[road.1].append(Edge(to: road.0, cost: road.2)) // 양방향 도로를 가정
}

// 출발 도시와 도착 도시
let start = 0
let end = 4
let minCost = dijkstra(start: start, end: end, graph: graph)

print("최소 비용: \(minCost)") // 출력: 최소 비용: 12
        

코드 설명

위의 스위프트 코드는 여러 함수를 사용하여 특정 도시에서 다른 도시로 가는 최소 비용을 찾는 알고리즘을 구현합니다.
각 도시부터 시작하는 dijkstra 함수는 graph 매개변수로 도시 연결 정보를 받고,
출발 도시와 도착 도시를 통해 최소 비용을 반환합니다.

1. Edge 구조체:
도시 간의 연결 정보를 저장합니다. to는 연결된 도시의 인덱스, cost는 해당 이동 비용입니다.

2. dijkstra 함수:
최소 비용을 계산하는 주 로직입니다. 시작 도시에서 인접한 도시를 탐색하며 최소 비용을 계속 업데이트합니다.
우선순위 큐를 사용하여 현재 도시에서 가장 가까운 도시로 다음 이동을 선택합니다.

3. 그래프 구조:
그래프는 인접 리스트 형태로 구축되며, 각각의 도시가 연결된 도로에 대한 정보를 포함합니다.

4. 결과: 주어진 시작 도시에서 도착 도시까지의 최소 비용을 출력합니다.

결과 분석

위 코드에서, 입력으로 주어진 도시와 도로 정보를 바탕으로 시작 도시인 0에서 도착 도시인 4까지 가는 최소 비용은 12로 계산됩니다.
이는 경로를 통해 이루어졌으며, 적절한 연결 및 비용 관리가 이루어졌음을 보입니다.
따라서 다익스트라 알고리즘을 통해 제공되는 최적화된 경로를 찾을 수 있음을 알 수 있습니다.

결론

본 강좌에서는 스위프트를 사용하여 최소 비용 구하기 문제를 해결하기 위해 다익스트라 알고리즘을 적용했습니다.
알고리즘의 이해와 함께 이를 실제 코드로 구현하는 방법을 익혔습니다.
알고리즘을 잘 이해하고 활용하면, 다양한 코딩테스트 및 실무에서도 유용하게 사용할 수 있는 기초가 될 것입니다.

추가적으로 더 복잡한 문제를 해결하기 위해 다양한 알고리즘을 익히고, 문제를 접할 때마다 끊임없이 연습하시기 바랍니다.
다음 강좌에서는 다른 알고리즘을 다루어 더 많은 문제를 해결해보고, 실력을 더욱 향상시켜 보겠습니다.