문제 링크

https://www.acmicpc.net/problem/1197

풀이

최소 스페닝 트리(MST)를 구하는 알고리즘은 2가지가 있음

쿠르스칼, 프림 해당 문제는 쿠르스칼로 풀었음

간선의 가중치로 정렬해 작은 가중치부터 점들을 이어 해당 노드가 이미 트리에 포함됬는지 않됬는지를 검사해 가면서 MST를 만들어 나가면 됨

노드에 포함되었는지 안되었는지는 Union-Find알고리즘을 사용

코드

import Foundation

var a:Int=0
var b:Int=0
var arr = [Int]()
if let inputs = readLine(){
    arr = inputs.split(separator: " ").map{(num) -> Int in return Int(num)!}
    a=arr[0]
    b=arr[1]
}

var board = [[Int]]()

for _ in 1...b{
    let arr = readLine()?.split(separator: " ").map{(num)->Int in return Int(num)!}
    board.append(arr!)
}
board.sort { a, b in
    return a[2]<b[2]
}

var check=[Int]()
for i in 0...a{
    check.append(i)
}
func union(_ a:Int,_ b:Int){
    let aParent = find(a)
    let bParent = find(b)
    if aParent<bParent{
        check[aParent]=bParent
    }
    else{
        check[bParent]=aParent
    }
}
func find(_ now :Int) -> Int{
    if check[now]==now{
        return now
    }
    let tmp = find(check[now])
    check[now]=tmp
    return tmp
}
var answer = 0

for i in 0..<b{
    let s = board[i][0]
    let f = board[i][1]
    let cost = board[i][2]
    
    if find(s) != find(f){
        union(s,f)
        answer += cost
    }
}
//print(check)
print(answer)