참조 링크 - 1
참조 링크 - 2

---

Disjoint Set

정의

서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조입니다.

• 전체 집합이 있을 때 구성 원소들이 겹치지 않도록 분할하는 데 자주 사용됩니다.
• 서로 다른 원소들이 같은 집합에 속애있는 지 판별하는 데 사용됩니다.

용어

• 셋(Set)은 개체들의 집합
• 셋 A 의 모든 원소가 셋 B에 포함될 때 부분집합이라고 합니다.
  • 이때, 셋 B는 셋 A의 초월집합이라고 합니다.
• 셋 A와 셋 B가 공유하는 원소가 하나도 없을 때 A와 B를 matually disjoint하다고 합니다.

예시

Set

• 셋 S : 1, 2, 3, 4
• 셋 A : 1, 2
• 셋 B : 3, 4
• 셋 C : 2, 3, 4
• 셋 D : 4

집합

• 셋 A, B, C, D 는 셋 S 의 부분집합
• 셋 S는 셋 A, B, C, D 의 초월집합
• 셋 A와 B는 matually disjoint하다

Union Find

• Disjoint set을 표현할 때 사용하는 자료구조

연산

• Union(합치기) : 두 원소 a, b가 주어질 때, 이들이 속한 두 집합을 하나로 합칩니다.
• Find(찾기) : 어떤 원소 a가 주어질 때, 이 원소가 속한 집합을 반환합니다.

---

구현 코드

test_case = int(input())


def find_parent(a):
    if parent[a] == a:
        return a
    else:
        p = find_parent(parent[a])
        parent[a] = p
        return p


def union(a, b):
    parent_a = find_parent(a)
    parent_b = find_parent(b)
    if parent_a != parent_b:
        parent[parent_b] = parent_a
        number[parent_a] += number[parent_b]


for _ in range(test_case):
    f = int(input())
    parent = dict()
    number = dict()
    for _ in range(f):
        a, b = input().split(" ")
        if a not in parent:
            parent[a] = a
            number[a] = 1
        if b not in parent:
            parent[b] = b
            number[b] = 1
        union(a, b)
        print(number[find_parent(a)])

• 위의 코드는 내가 백준 알고리즘 문제에서 풀었던 풀이 코드이다.
• 해당 문제의 링크는 이곳 으로 가면 됩니다.

---

자료구조는 알고리즘을 푸는 데에 있어서 도구로 사용된다라는 말이 점점 체감이 되기 시작한다.
앞으로는 자료구조 공부를 할 때에는, 자료구조의 종류만 공부를 하는 것이 아니라, 해당 자료구조를 어떻게 사용하면 될 지에 대해서도 공부를 해야겠다.
어떠한 자료구조를 공부했을 때에 동시에 그 자료구조를 활용하는 알고리즘을 하나씩 풀어보면 더욱 도움이 될 것 같다.
열심히 해보자!