Algorithm :: 집합의 표현 (union-find)

백준 문제 : (1717) 집합의 표현
알고리즘 : Union-Find

문제 정리

1. 집합 n+1개 ({0},{1},{2},…{n})
2. 첫 줄에 n과 m이 주어짐
3. n은 집합의 개수이며 m은 라인
4. 각 라인은 [0 1(a) 3(b)], [1 7 1]가 같이 3개의 숫자를 전달
5. 맨 앞의 숫자 0은 a와 b를 합치며 1은 두 집합이 같은 집합인지 판단하여 “YES, “NO”를 출력

   1 2 3 4 5 6 7 8 9 10

   입력 출력 7 8 NO 0 1 3 NO 1 1 7 YES 0 7 6 1 7 1 0 3 7 0 4 2 0 1 1 1 1 1

문제 해석

1. 초기에 주어지는 n은 makeset으로 서로소 집합으로 초기화 한다.
2. 1이 주어질 때마다 각 루트를 찾아야 하므로 union-find 알고리즘을 사용하여 해결한다.

Brute force

문제를 읽고 제일 쉽게 접근할 수 있는건 Linked List 일 것이다. Linked List는 내부에 다음 노드에 대한 정보를 갖고 있기 때문에 다음 노드를 참조하여 쉽게 루트까지 접근할 수 있다. 하지만 문제에서 주어지 듯 노드의 개수가 많아지면 많아질 수록 이 방법으론 원하는 속도로 해결하기 쉽지 않은데 Linked List로 해결할 때 시간 복잡도가 O(n)이기 때문이다.

union-find

집합들을 합치고 그 집합들의 루트를 쉽게 찾을 수 있는 자료구조이다. 이 자료구조는 두 개의 유용한 연산을 제공하는데 다음과 같다.

• find : 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환
• union : 두 개의 집합을 하나의 집합으로 합침

union-find는 트리로 표현되는 자료구조이며 최적화까지 적용한 시간복잡도는 O(logn)으로 굉장히 빠른 속도를 보여줘 원하는 시간 내로 문제를 해결할 수 있다.

find(x)는 주어진 원소의 루트(대표) 집합을 찾는 함수인데 루트가 자기 자신일 때까지 재귀함수를 통해 찾아나가며 이때 속도를 더 향상 시키기 위해 주어진 원소가 바로 루트를 바라볼 수 있게 값을 저장한다.

union(x, y)는 find를 통해 얻어진 두 개의 루트끼리 비교하여 다를 경우 한 개의 집합을 다른 집합의 일부로 저장하도록 한다. 특별한 기준없이 저장할 경우 한 쪽의 트리가 너무 커지기 때문에 트리의 깊이를 맞춰줄 수 있도록 기능을 추가하면 더 빠르게 탐색이 가능하다. (여기서는 특별히 다루지 않는다)

문제 소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

fun main() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val dt = IntArray(n + 1) { it }

    fun find(x: Int): Int {
        if (dt[x] == x) return x
        dt[x] = find(dt[x])
        return dt[x]
    }
    
    fun union(x: Int, y: Int) {
        dt[find(y)] = find(x)
    }
    
    repeat(m) {
        val (cmd, a, b) = readLine()!!.split(" ").map { it.toInt() }
        when(cmd) {
            0 -> union(a, b)
            1 -> println(if (find(a) == find(b)) "YES" else "NO")
        }
    }
}

• readLine()!!.split(" ").map{ it.toInt() }는 라인으로 들어오는 INPUT 데이터를 정수형 타입으로 변환
• IntArray(n + 1) { it }는 makeset으로 서로소 집합으로 초기화 하는 작업
• find, union는 union-find를 구현하기 위한 기본 함수들