BOJ-1717 집합의 표현 Swift

문제

초기에 𝑛+1개의 집합 {0},{1},{2},…,{𝑛}이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 𝑛, 𝑚이 주어진다. 𝑚은 입력으로 주어지는 연산의 개수이다. 다음 𝑚개의 줄에는 각각의 연산이 주어진다. 합집합은 0 𝑎 𝑏의 형태로 입력이 주어진다. 이는 𝑎가 포함되어 있는 집합과, 𝑏가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 𝑎 𝑏의 형태로 입력이 주어진다. 이는 𝑎와 𝑏가 같은 집합에 포함되어 있는지를 확인하는 연산이다.

출력

1로 시작하는 입력에 대해서 𝑎와 𝑏가 같은 집합에 포함되어 있으면 "YES" 또는 "yes"를, 그렇지 않다면 "NO" 또는 "no"를 한 줄에 하나씩 출력한다.

내가 푼 풀이

문제 자체는 어려워보이지 않았다

 

접근방법: Dictionary 자료구조 이용(실패)

- 딕셔너리를 이용하려고 했는데 알고보니 문제를 잘 이해하지 못하고 도전했다.

- 합집합을 한 결과가 해당 집합이 되는줄 알고, 예로 1과 3을 합집합연산하면 (1,3), (3,1)이 생기는줄 알았다.

 

접근방법: Union-Find

- 주어진문제에서 서로다른 원소들은 전체집합을 이루고, 합집합을 한다면 union으로 합쳐주고, 같은 원소인지 판단하려면

두개의 해당 원소들의 루트노드가 같은지 확인하면 됬다.

- 이번 기회에 Union-Find 알고리즘을 알게되었는데, 서로소 집합에대해 포함하는지 효율적으로 탐색할 수 있다고 알게되었다.

 

코드로 구현하면 다음과 같다.

import Foundation

// 입력받기
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = input[0], m = input[1]
// Union-Find
// 처음의 원소는 자기 자신을 루트노드로 갖는다.
// parent[x] = a: x의 부모노드는 a다.
var parent = Array(repeating: 0, count: n+1)
for i in 1...n {
    parent[i] = i
}
// 두개의 서로소집합을 합친다.
// 단순히 y의 루트노드가 x를 가리키면 된다.
// 이 문제에서는 연산의 크기가 크지않아서 따로 설정하지 않았지만, 이 알고리즘은 트리의 depth에 따라 연산속도가 달라진다.
// 그래서 합치는 과정에서 depth가 큰노드가 작은노드를 루트노드로 합치는 방향이 더 좋다.
func union(_ x: Int, _ y: Int) {
    var rootX = find(x)
    var rootY = find(y)
    parent[rootY] = rootX
}
// 해당 원소의 루트노드를 찾을때까지 재귀호출
func find(_ x: Int) -> Int {
    if parent[x] == x { return x}
    parent[x] = find(parent[x])
    return parent[x]
}
// 연산 실행
for i in 0..<m {
    let op = readLine()!.split(separator: " ").map{Int(String($0))!}
    // 합집합은 서로 합쳐준다.
    if op[0] == 0 {
        union(op[1], op[2])
    } else {
        // 두 원소가 같은 집합에 있다는것은 둘다 같은 루트노드를 가리킴을 의미한다.
        let p1 = find(op[1])
        let p2 = find(op[2])
        print(p1 == p2 ? "YES" : "NO")
    }
}