1. 문제 설명

최소 스패닝 트리

2. 문제 분석

크루스칼 알고리즘을 통해 최소 스패닝 트리 비용을 구한다.

• 스위프트에서 구현한 크루스칼 알고리즘에서 비용 순서대로 간선을 정렬해 하나씩 확인하는데, 내장 모듈에 힙이 없기 때문에(파이썬에서는 힙을 사용했다) 배열에 간선 저장 후 정렬한 결과를 반복문을 통해 확인했다.

3. 나의 풀이

import Foundation

let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
var pq = [(Int, Int, Int)]()
for _ in 0..<M{
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let (node1, node2, cost) = (input[0], input[1], input[2])
    pq.append((cost, node1, node2))
}
pq.sort(by:{$0.0 < $1.0})
var parents:[Int] = []
for i in 0..<(N+1){
    parents.append(i)
}

let MST = Kruskal()
print(MST)

func find(node:Int)->Int{
    if parents[node] == node{
        return node
    } else {
        parents[node] = find(node:parents[node])
        return parents[node]
    }
}

func union(node1: Int, node2: Int) -> Bool{
    let root1 = find(node:node1)
    let root2 = find(node:node2)
    if root1 == root2{
        return false
    } else {
        parents[root2] = root1
        return true
    }
}

func Kruskal() -> Int{
    var total = 0
    var edgeCnt = 0
    for curData in pq{
        let cost = curData.0
        let node1 = curData.1
        let node2 = curData.2
        
        if union(node1: node1, node2: node2) == true{
            total += cost
            edgeCnt += 1
            if edgeCnt == N-1{
                return total
            }
        }
    }
    return -1
}