Swift) 프로그래머스 네트워크 - Lv. 3

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

프로그래머스

문제 풀이: 서로 연결되어있는 컴퓨터의 네트워크 개수, 즉 집합이 몇개 있는지를 물어보는 문제. Union ford 알고리즘을 이용해 풀었다. 한가지 주의할 점은 마지막에 각 컴퓨터가 연결되어있는 부모가 어떤것인지 체크하는 작업을 해 주어야지 정확한 네트워크 개수가 나온다.

import Foundation

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    var parents = Array(0..<n)
    func getparent(_ num: Int) -> Int {
        if parents[num] == num {
            return num
        }
        return getparent(parents[num])
    }
    
    func unionParent(_ a: Int, _ b: Int) {
        let aParent = getparent(a)
        let bParent = getparent(b)
        if aParent < bParent {
            parents[bParent] = aParent
        } else {
            parents[aParent] = bParent
        }
    }
    for i in 0..<n {
        for j in 0..<n {
            if i == j {
                continue
            }
            if computers[i][j] == 1 {
                unionParent(i, j)
            }
        }
    }
    var ansParents: [Int] = []
    for i in 0..<n {
        ansParents.append(getparent(i))
    }
    return Set(ansParents).count
}