[Swift 알고리즘] 네트워크 - 프로그래머스

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

---

접근 방법

[i][j] 값이 1인 연결 행렬을 받아서, 서로소 집합의 개수를 센다.
Union-Find로 풀이하면 될 듯
시간복잡도는 최악의 경우 Union과 Find 각각 O(N)에 준하는 수준이다.

의사 코드

크기가 n인, 루트 노드의 정보를 담는 배열 생성
find()를 정의. 시간복잡도를 위해 경로 압축한 형태로.
union()을 정의. 노드 번호가 빠른 것이 루트 노드로 갈 수 있도록 구현
computers를 탐색하여, i != j인 경우, union 연산을 실행
루트 노드의 정보를 Set으로 변환하여 네트워크가 몇 가지인지 return

나의 풀이 + chatGPT

import Foundation

func find(_ x: Int, _ rootArr: inout [Int]) -> Int {
    if rootArr[x] != x {
        rootArr[x] = find(rootArr[x], &rootArr)
    }
    return rootArr[x]
}

func union(_ x: Int, _ y: Int, _ rootArr: inout [Int]) {
    let rootX = find(x, &rootArr)
    let rootY = find(y, &rootArr)
    if rootX < rootY {
        rootArr[rootY] = rootX
    } else {
        rootArr[rootX] = rootY
    }
}

func solution(_ n: Int, _ computers: [[Int]]) -> Int {
    var rootArr = Array(0..<n)

    for i in 0..<n {
        for j in 0..<n {
            if i != j {
                union(i, j, &rootArr)
            }
        }
    }

    let uniqueNetworks = Set(rootArr.map { find($0, &rootArr) }) // 헷갈린 부분
    return uniqueNetworks.count
}

 

도움을 받은 부분은 uniqueNetworks 변수를 초기화 할 때, rootArr의 각 원소에 find() 함수를 적용하는 부분이다.

find() 함수에서 이미 경로 압축을 진행했기에, 다시 find()를 하는 과정이 필요 없을 것이라고 판단했다.

그러나 union() 연산을 적용하지 않는 원소가 있는 경우, 반드시 해당 원소들에 대해서도 find() 연산을 적용해야 한다.

 

참고

Union-Find 개념: https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

Union-Find 시간 복잡도: https://8iggy.tistory.com/157