백준 - 최소 스패닝 트리 (1197)

struct Edge {
    let start: Int
    let end: Int
    let value: Int
}

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (V, E) = (input[0], input[1])
var queue = Heap<Edge>(sort: { $0.value < $1.value }) // 에지 저장하는 우선순위 큐
var parent = Array(0...V)

for _ in 0..<E {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    queue.insert(Edge(start: input[0], end: input[1], value: input[2]))
}

// 크루스칼 알고리즘 실행
var count = 0
var answer = 0

while count < V - 1 {
    let now = queue.remove()!
    if find(now.start) != find(now.end) {
        union(now.start, now.end)
        count += 1
        answer += now.value
    }
}

print(answer)

// 유니온 파인드 관련 함수
func union(_ a: Int, _ b: Int) {
    let aParent = find(a)
    let bParent = find(b)
    if aParent < bParent {
        parent[bParent] = aParent
    } else {
        parent[aParent] = bParent
    }
}

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

크루스칼 알고리즘을 사용하여 최소 신장 트리를 구현하는 기본적인 문제였다.

가중치가 가장 작은 에지를 찾기 위해 우선순위 큐를 사용하고, 사이클 여부를 검사하기 위해 유니온 파인드를 구현 및 사용한다.