백준 1717 집합의 표현

출처: https://www.acmicpc.net/problem/1717

분류: 자료구조

---

접근방식

몰랐는데 disjoint-set(서로소 집합) 문제라고 하네요.

집합이 합쳐지는 걸 어떤 집합에 속하게 된다는 개념으로 접근하면 쉽게 해결할 수 있는 문제였습니다.

배열에는 부모를 저장하고 있고 재귀적으로 최상위 부모를 찾아서 비교하고,
합칠 때도 역시 최상위 부모로 합쳐주면 됩니다 :)

처음엔 문제 그대로 집합을 합쳐주고 원소들을 합쳐진 집합으로 다 바꿔주는 식으로.... 1차원적으로 풀었는데 당연히 시간초과였습니다 흡

* a와 b를 확인하기 전에 같은 경우를 걸러주면 시간을 많이 줄일 수 있습니다 :)

해결방법

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
var parents = Array(0...input[0])

func parent(of i: Int) -> Int {
    guard parents[i] != i else { return i }
    parents[i] = parent(of: parents[i])
    return parents[i]
}

func union(_ a: Int, _ b: Int) {
    let aParent = parent(of: a)
    let bParent = parent(of: b)
    guard aParent != bParent else { return }
    parents[bParent] = aParent
}

for _ in 0..<input[1] {
    let order = readLine()!.split(separator: " ").map { Int(String($0))! }
    let a = order[1]
    let b = order[2]
    
    if order[0] == 0 {
        guard a != b else { continue }
        union(a, b)
    } else {
        print(parent(of: a) == parent(of: b) ? "YES" : "NO")
    }
}

배운점

또 하나 배워간다. 워낙 유명하고 대표적인 문제 같은데 처음본다; 갈 길이 머~~~~~ㄹ다 

union에서 parents[bParent]로 해야하는데 그냥 parents[b]로 해서 한 시간을 날려먹었다..... ㅠ