스위프트 코딩테스트 강좌, 최소 신장 트리

문제 설명

회사가 여러 도시를 연결하는 네트워크를 구성하려고 합니다. 각 도시 사이의 도로는 비용이 발생합니다. 모든 도시를 연결하되 비용을 최소로 줄이기 위해 회사는 어떤 도로를 선택해야 할까요?

도시와 도로의 정보를 담고 있는 그래프가 주어질 때, 최소 신장 트리를 구하는 문제를 해결해야 합니다.

입력 형식

            첫째 줄에 도시의 개수 N (2 ≤ N ≤ 1000)과 도로의 개수 M (1 ≤ M ≤ 10000)이 주어집니다.
            이어서 M개의 줄에 각 도로와 그 가중치가 주어집니다. 
            도로의 정보를 (A, B, C) 형태로 나타내며, A와 B는 도시의 번호, C는 도로의 비용입니다.
            

출력 형식

            최소 신장 트리를 구성하는 데 필요한 총 비용을 출력합니다.
            

문제 해결 과정

1단계: 알고리즘 선택

이 문제는 크루스칼 알고리즘을 사용하여 해결할 수 있습니다. 크루스칼 알고리즘은 그래프의 모든 간선을 가중치의 오름차순으로 정렬한 후, Union-Find 자료구조를 사용하여 사이클을 체크하며 최소 신장 트리를 구성해 나가는 방식입니다.

2단계: 데이터 구조 설계

Union-Find 자료구조를 사용하기 위해 두 가지 배열을 만듭니다: parent와 rank. parent는 각 노드의 부모를 나타내고, rank는 트리의 높이를 나타냅니다. 이 데이터를 활용하여 노드의 연결 상태를 관리합니다.

            // Union-Find 구조체
            struct UnionFind {
                var parent: [Int]
                var rank: [Int]

                init(size: Int) {
                    parent = Array(0.. Int {
                    if parent[u] != u {
                        parent[u] = find(parent[u])
                    }
                    return parent[u]
                }

                mutating func union(_ u: Int, _ v: Int) {
                    let rootU = find(u)
                    let rootV = find(v)

                    if rootU != rootV {
                        if rank[rootU] > rank[rootV] {
                            parent[rootV] = rootU
                        } else if rank[rootU] < rank[rootV] {
                            parent[rootU] = rootV
                        } else {
                            parent[rootV] = rootU
                            rank[rootU] += 1
                        }
                    }
                }
            }
            

3단계: 크루스칼 알고리즘 구현

모든 간선을 가중치 기준으로 정렬한 다음, 순서대로 간선을 선택하면서 사이클을 형성하지 않는 경우에만 선택합니다. 이 과정을 통해 최소 신장 트리를 구성하고 이때의 가중치 합을 계산합니다.

            func kruskal(n: Int, edges: [(Int, Int, Int)]) -> Int {
                var uf = UnionFind(size: n)
                var totalCost = 0
                let sortedEdges = edges.sorted { $0.2 < $1.2 }
                
                for edge in sortedEdges {
                    let (u, v, cost) = edge
                    if uf.find(u) != uf.find(v) {
                        uf.union(u, v)
                        totalCost += cost
                    }
                }
                return totalCost
            }
            

4단계: 테스트 및 결론

이제 입력을 받아서 kruskal 함수에 전달하고 결과를 출력해봅니다.

            let n = 4
            let edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
            let minCost = kruskal(n: n, edges: edges)
            print("최소 신장 트리의 비용: \(minCost)")
            

위 예시는 최소 신장 트리의 총 비용을 출력해줍니다.