Union-Find (Disjoint-Set) Data Structure -1

1. Union-Find 란?

Union-Find는 disjoint(겹치지 않는) 집합들의 모음을 관리하는 자료 구조이다. 각 요소는 하나의 집합에 속하며, 초기에는 각 요소가 독립적인 단일 집합으로 시작한다.

• 전체 원소는 n개로 구성되며, 이름은 0, 1, …, n-1로 지정된다
• 각 원소는 정확히 하나의 집합에 속한다.
  • 집합들은 서로소(겹치지 않는) 상태이다.
  • 초기에는 각 집합이 단일 원소로 이루어진 독립적인 집합(singleton)이다.
• 각 집합은 대표 원소(representative member)를 가진다. (집합 내의 어떤 원소든 대표로 사용할 수 있다.)

Union/Find operations은 아래와 같이 4개정도가 있다.

void init(int n)

void union(int p, int q)

int find(int p)

boolean in_same_set(int p, int q)

 

이 중 주요 연산으로는 Union과 Find가 있다.

• Union: 두 집합을 합칩니다.

• Find: 특정 요소가 속한 집합의 대표자(representative)를 찾습니다.

 

2. Union-Find의 Data Structure

자료구조 : 불연속 집합 트리(disjoint-set forest)형태로 표현

 

해당 트리의 각 노드(node)는 부모(parent)를 가리키는 포인터를 가지고 루트 노드는 자기 자신을 가리키거나, NULL과 같은 특별한 값을 가진다. 트리의 루트 노드가 해당 집합의 대표자 역할을 한다. 즉, 하나의 트리는 하나의 집합을 나타내며, 트리의 모든 노드는 집합의 구성원이고, 트리의 루트 노드는 집합의 대표자가 된다.

예를 들어 {1, 5, 8}로 구성된 집합과 {2, 0, 4, 3, 6, 9}로 구성된 집합, {7}로 구성된 집합이 있을 때 불연속 집합 트리를 사용하여 다음과 같이 표현할 수 있다. 

 

 

이러한 표현 방식은 데이터 구조는 트리 기반 표현을 통해 유니온 및 파인드 연산을 효율적으로 수행할 수 있도록 설계되었다.

 

3. 배열로 표현하기

Union-Find에서 트리 구조는 배열을 사용해 표현한다.

이를 통해 트리의 부모 관계를 간단히 나타내고, 연산을 효율적으로 처리할 수 있다. 각 배열의 인덱스 i는 트리의 노드(원소)를 나타내고 배열의 값 pt[i]는 노드 i의 부모 노드를 가리킨다. 배열의 길이는 n이며, 각 인덱스 i는 원소 i의 부모 노드(parent)를 나타낸다. 특정 노드의 루트는 pt[pt[...pt[i]...]] 방식으로 반복적으로 부모를 따라 올라가 확인한다.

예를 들어 정수 배열 pt[]를 사용해서 위의 트리구조를 표현해보면, 아래와 같이 나타낼 수 있다. pt[5] = 1로 5의 부모가 1임을 나타낸다.

0의 부모노드는 4이다. 

1의 부모노드는 1이다.  ➞ 루트노드 

2의 부모노드는 0이다. 

3의 부모노드는 4이다. 

4의 부모노드는 4이다. ➞ 루트노드 

5의 부모노드는 1이다. 

6의 부모노드는 3이다.

7의 부모노드는 7이다.  ➞ 루트노드 

8의 부모노드는 5이다. 

9의 부모노드는 3이다. 

 

이렇게 부모노드를 따라가면 루트노드를 확인할 수 있고 각 집합을 구별할 수 있다.

 

 

4.Union/Find operations

그렇다면, 프로그램으로 어떻게 루트 노드를 찾고 같은 집합인지 확인할 수 있을까?

 Find 연산과 In_same_set 연산을 사용하면된다. Find연산으로 특정 노드의 루트를 찾고  In_same_set 연산으로두 노드의 루트가 같은지 비교하여 동일 집합 여부를 확인하면 된다. 

 1. Find 연산 : 특정 노드 p가 속한 집합의 대표 노드(루트)를 찾음

• 방법:
  • p에서 시작하여 pt[i] 배열을 따라가며 부모 노드를 반복적으로 탐색
  • 루트 노드는 자기 자신을 부모로 가리키므로, 이를 기준으로 탐색 종료.
•  예시:
  • 5의 루트를 찾는 과정:
    • 1. pt[5] = 1 (부모는 1)
    • 2. pt[1] = 1 (루트는 1)
    •  결과: 루트는 1.
  • 9의 루트를 찾는 과정:
    • 1. pt[9] = 4 (부모는 4)
    • 2. pt[4] = 4 (루트는 4)
    • 결과: 루트는 4.

def find(pt, x):
    while pt[x] != x:  # 부모가 자기 자신이 아니면 반복
        x = pt[x]  # 부모로 이동
    return x  # 루트를 반환

 

 2.  In_same_set 연산: 두 원소 p와 q가 같은 집합에 속하는지 확인하려면 루트 노드가 같은지 비교

• 방법:
  •  p의 루트를 찾고, q의 루트를 찾은 뒤 두 값을 비교.
•  예시:
  • 5와 9 :
  • 5의 루트: 1
  • 9의 루트: 4
  • 결과: 루트가 다르므로 5와 9는 같은 집합에 속하지 않음.

def in_same_set(pt, p, q):
    return find(pt, p) == find(pt, q)  # 두 노드의 루트가 같은지 비교

 

 

두 집합을 병합하는 방법도 알아보자.

3. Union연산 : 두 원소 p와 q가 각각 속한 집합을 병합하여 하나의 집합으로 만듦.

• 방법 : 
  • p와 q의 루트를 찾음
  • 두 루트 중 하나의 루트를 다른 루트의 부모로 설정하여 두 트리를 병합
• 예시 : 
  • 초기 상태: 
    • p = 5, q = 9
    • 5의 루트: 1, 9의 루트: 4
  • union(5, 9) 호출:
    • 5의 루트 1을 9의 루트 4의 자식으로 설정.
    • 결과: 1과 4가 연결되며 두 집합이 병합.
    •  
  • 변화된 pt 배열:
    • pt[1] = 4로 변경됨.

def union(pt, p, q):
    # p와 q의 루트를 찾음
    rootP = find(pt, p)
    rootQ = find(pt, q)
    # 루트가 다르면 병합
    if rootP != rootQ:
        pt[rootP] = rootQ  # p의 루트를 q의 루트에 연결

 

4. init 연산 : n개의 원소가 각각 독립적인 집합(singleton)을 이루도록 초기화.

각 원소는 자신의 부모를 자신으로 설정.

 

• 방법 : 
  • 배열 pt에서, 각 인덱스 i가 원소를 나타내며, 초기에는 pt[i] = i로 설정.
  • 이는 모든 노드가 루트가 되는 n개의 독립적인 트리를 생성.
• 예시 : 
  • 초기화 후, n = 10일 때 pt 배열은 다음과 같이 구성된다.
  • pt[0] = 0, pt[1] = 1, …, pt[9] = 9
  • 즉, 각 노드는 자기 자신을 부모로 가리키며, 서로 독립적인 집합을 형성

 

def init(n):
    return [i for i in range(n)]  # 초기화

 이처럼, 배열을 사용해서 트리구조를 나타내면 실제 트리를 저장하지 않고 배열 하나로 트리를 표현할 수 있어 공간 효율성이 좋다.  Find 연산은 부모 배열을 순회하여 루트에 도달하기만 하면 되기 때문에 연산이 간단하다는 장점이 있다. 

def init(n):
    return [i for i in range(n)]  # 초기화

def find(pt, x):
    while pt[x] != x:  # 루트 노드에 도달할 때까지 부모 따라가기
        x = pt[x]
    return x

def in_same_set(pt, p, q):
    return find(pt, p) == find(pt, q)  # 같은 집합 여부 확인

def union(pt, p, q):
    rootP = find(pt, p)
    rootQ = find(pt, q)
    if rootP != rootQ:
        pt[rootP] = rootQ  # 병합