[백준] 4195번 / 친구 네트워크 (Swift)

https://www.acmicpc.net/problem/4195

4195번: 친구 네트워크

• Union-Find 알고리즘을 사용하여 풀어야 하는데, Union-Find 알고리즘은 원소들의 연결 여부를 확인하는 알고리즘이다.
• Find 함수 : 파라미터의 루트 부모를 찾음 (재귀로 찾음)
• Union 함수 : 오른쪽 파라미터의 루트 부모를 왼쪽의 루트 부모로 만듬 (즉 왼쪽 루트 부모가 제일 최강 루트 부모가 되는것)
• 친구 관계가 생길때마다 네트워크 수는 Union함수가 호출될때마다, 왼쪽루트 부모의 네트워크 수 + 오른쪽 루트 부모의 네트워크 수

import Foundation

let testCase = Int(readLine()!)!

for _ in 0..<testCase {
    let relationShipCount = Int(readLine()!)!
    
        var parentDic = [String: String]()
        var count = [String: Int]()
        
        func find(_ x: String) -> String {
            if x == parentDic[x]! {
                return x
            } else {
                let routeParent = find(parentDic[x]!)
                parentDic[x] = routeParent
                return parentDic[x]!
            }
        }
        
        func union(_ x: String, _ y: String) {
            let parentX = find(x)
            let parentY = find(y)
            
            if parentX != parentY {
                parentDic[parentY] = parentX
                count[parentX]! += count[parentY]! // 왼쪽루트 부모의 네트워크 수 + 오른쪽 루트 부모의 네트워크 수
            }
        }
    for _ in 0..<relationShipCount {
        let names = readLine()!.split(separator: " ").map{String($0)}
        let left = names[0]
        let right = names[1]
        
        if parentDic.keys.contains(left) == false {
            parentDic[left] = left
            count[left] = 1
        }
        
        if parentDic.keys.contains(right) == false {
            parentDic[right] = right
            count[right] = 1
        }
        
        union(left, right)
        print(count[find(left)]!)
    }
}