1. 문제 설명

전력망을 둘로 나누기

2. 문제 분석

Union-Find를 통해 해당 노드의 루트 노드를 구하는 데, 특정 간선을 끊은 시점(즉 사용하지 않은 시점)마다 골라야 하기 때문에 간선의 개수만큼 Union-Find를 해야 한다. 이를 통해 해당 간선을 끊은 경우의 컴포넌트에 속하는 노드의 개수를 구할 수 있으므로, 최솟값을 리턴한다.

3. 나의 풀이

import Foundation

func solution(_ n:Int, _ wires:[[Int]]) -> Int {
   var parents = Array(repeating: 0, count: n+1)
   func resetNodes() {
       for idx in 0..<n+1 {
           parents[idx] = idx
       }
   }
   
   func find(node: Int) -> Int {
       if parents[node] == node {
           return node
       } else {
           parents[node] = find(node: parents[node])
           return parents[node]
       }
   }
   
   func union(node1: Int, node2: Int) -> Bool {
       let root1 = find(node: node1)
       let root2 = find(node: node2)
       if root1 == root2 {
           return false
       } else {
           if root1 > root2 {
               parents[root2] = root1
           } else {
               parents[root1] = root2
           }
           return true
       }
   }
   
   func getComponentsDiff() -> Int {
       var nodeDict = [Int:Int]()
       for idx in 1..<parents.count {
           let root = find(node: parents[idx])
           let count = nodeDict[root] ?? 0
           nodeDict[root] = count + 1
       }
       let values = Array(nodeDict.values)
       return abs(values[0] - values[1])
   }
   
   var answer = Int.max
   for cut in 0..<wires.count {
       resetNodes()
       for idx in 0..<wires.count {
           if idx == cut {
               continue
           }
           let wire = wires[idx]
           let (parent, child) = (wire[0], wire[1])
           union(node1: parent, node2: child)
       }
       answer = min(answer, getComponentsDiff())
   }
   return answer
}