[백준][BOJ1717] 집합의 표현

1. 문제 : https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

---

2. 풀이 : Union-Find

---

3. 시간복잡도 : O(logN)

---

4.설명

최초 각 원소는 자기 자신을 대표값으로 갖는 집합으로 그림[1]과 같이 표현된다.

그림 [1]

2번 원소 집합을 1번 원소 집합의 대표값에 연결하여 집합을 합치면 그림[2]와 같이 표현된다. (2번 원소 집합의 대표값을 1로 변경)

그림[2]

그림[2]에서 1번 원소 집합의 대표값(1)과 2번 원소 집합의 대표값(1)이 같으므로 서로 같은 집합이다.

그림[2]에서 1번 원소 집합의 대표값(1)과 3번 원소 집합의 대표값(3)이 다르므로 서로 다른 집합이다.

2번 원소 집합과 3번 원소 집합을 합치고, 3번 원소 집합과 4번 원소 집합을 합치면 그림[3]과 같이 표현된다.

그림[3]

그림[3]에서 4번 원소 집합의 대표값은 3->2->1 탐색에 의해서 1임을 알 수 있고, 1번 원소 집합의 대표값과 같으므로 4번 원소와 1번 원소는 서로 같은 집합이다.

그림[3]처럼 트리(집합)의 깊이가 깊어질수록 탐색 시간이 늘어나므로 그림[4]와 같이 트리의 높이를 조정하여 탐색 시간을 줄이는 최적화 작업을 한다.

그림[4]

그림[4]에서의 집합은 {1, 2, 3, 4}, {5}, {6}, {7} 이다.

그림[5]

그림[5]와 같이 두 개의 트리를 합칠 때, 높이가 높은 트리에 높이가 낮은 트리를 붙임으로써 트리의 높이를 낮게 유지 할 수 있다.

그림[6]은 높이가 높은 트리에 높이가 낮은 트리를 붙인 경우와, 높이가 낮은 트리에 높이가 높은 트리를 붙인 경우를 보여준다.

그림[6]

그림[7]과 같이 높이가 같은 두 트리를 합치는 경우는 무조건 트리의 높이가 1 증가함을 알 수 있다.

그림[7]

---

5. 코드