Swift) 프로그래머스 섬 연결하기 - Lv. 3

https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

문제 풀이: UnionFord 알고리즘을 기반으로한 크루스칼 알고리즘을 이용한 풀이. 경로를 가중치 순서대로 정렬 한 후, 가장 저렴한 경로부터 선택한다. 이때, 사이클이 만들어지는지 확인. 연결하려고 하는 노드와 연결되는 노드간에 부모가 같다면 사이클이 생기는 것 이므로 unionFord 알고리즘을 이용해 부모를 확인한다.

import Foundation
var parents: [Int] = []

func getParent(_ num: Int) -> Int {
    if parents[num] == num {
        return num
    }
    return getParent(parents[num])
}

func union(_ num1: Int, _ num2: Int) {
    let firstParent = getParent(num1)
    let secondParent = getParent(num2)
    if firstParent < secondParent {
        parents[secondParent] = firstParent
    } else {
        parents[firstParent] = secondParent
    }
}

func findParent(_ num1: Int, _ num2: Int) -> Bool {
    let firstParent = getParent(num1)
    let secondParent = getParent(num2)
    return firstParent == secondParent
}

func solution(_ n:Int, _ costs:[[Int]]) -> Int {
    let sortedCosts = costs.sorted{ $0[2] < $1[2] }
    parents = Array(0..<n)
    var sum = 0
    for i in 0..<sortedCosts.count {
        if !findParent(sortedCosts[i][0], sortedCosts[i][1]) {
            sum += sortedCosts[i][2]
            union(sortedCosts[i][0], sortedCosts[i][1])
        }
    }
    return sum
}