42861. 섬 연결하기

[ghis22130]

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

[ghis22130]

https://ghis22130.github.io/2021-07-12-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4_%ED%83%90%EC%9A%95%EB%B2%95_-%EC%84%AC%EC%97%B0%EA%B2%B0%ED%95%98%EA%B8%B0/

[lenaios]

블로그가 많은 도움이 되었습니다. Kruskal 알고리즘을 이용하는 문제네요. 어렵..😥

import Foundation

var parent: [Int] = []
func solution(_ n:Int, _ costs:[[Int]]) -> Int {
    var sum = 0
    parent = Array(0..<n)
    let sorted = costs.sorted { $0[2] < $1[2] }
    for arr in sorted {
        if !isCycled(arr[0], arr[1]) {
            connect(arr[0], arr[1])
            sum += arr[2]
        }
    }
    return sum
}

func isCycled(_ island1: Int, _ island2: Int) -> Bool {
    return parent[island1] == parent[island2]
}

func connect(_ island1: Int, _ island2: Int) {
    let temp = parent[island2]
    parent[island2] = parent[island1]
    // parent 변경 시 이미 변경되어있던 것들도 갱신 필요
    for i in 0..<parent.count {
        if parent[i] == temp {
            parent[i] = parent[island1]
        }
    }
}