[알고리즘] 서로소 집합 (Disjoint Sets)

Algorithm

[알고리즘] 서로소 집합 (Disjoint Sets) - 자료구조

bu119 2023. 12. 9. 21:20

728x90

그래프

그래프(Graph)란 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조를 의미한다.

서로소 집합

서로소 집합(Disjoint Sets)이란 공통 원소가 없는 두 집합을 의미한다.

서로소 집합 자료구조

서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다.
서로소 집합 자료구조는 두 종류의 연산을 지원한다.
- 합집합(Union): 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다.
- 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다.

서로소 집합 자료구조는 합치기 찾기(Union Find) 자료구조라고 불리기도 한다.

1. 여러 개의 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작 과정

합집합(Union) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인합니다.
1. A와 B의 루트 노드 A′, B′를 각각 찾습니다.
2. A′를 B′의 부모 노드로 설정합니다.
모든 합집합(Union) 연산을 처리할 때까지 1번의 과정을 반복합니다.

2. 동작 과정 살펴보기

이러한 4개의 union 연산은 각각 '1과 4는 같은 집합', '2와 3은 같은 집합', '2와 4는 같은 집합', '5와 6은 같은 집합'이라는 의미를 가지고 있다.

일반적으로 합치기 연산을 수행할 때, 더 큰 루트 노드가 더 작은 노드를 가리키도록 만들어서 테이블을 갱신한다.

3. 서로소 집합 자료구조: 연결성

서로소 집합 자료구조에서는 연결성을 통해 손쉽게 집합의 형태를 확인할 수 있습니다.

기본적인 형태의 서로소 집합 자료구조에서는 루트 노드에 즉시 접근할 수 없습니다.
- 루트 노드를 찾기 위해 부모 테이블을 계속해서 확인하며 거슬러 올라가야 합니다.

다음 예시에서 노드 3의 루트를 찾기 위해서는 노드 2를 거쳐 노드 1에 접근해야 합니다.

4. 서로소 집합 자료구조: 기본적인 구현 방법 (코드)

1) 서로소 집합 자료구조: 기본적인 구현 방법 (Python)

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return x

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화하기

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

# Union 연산을 각각 수행
for i in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)

# 각 원소가 속한 집합 출력하기
print('각 원소가 속한 집합: ', end='')
for i in range(1, v + 1):
    print(find_parent(parent, i), end=' ')

print()

# 부모 테이블 내용 출력하기
print('부모 테이블: ', end='')
for i in range(1, v + 1):
    print(parent[i], end=' ')

2) 서로소 집합 자료구조: 기본적인 구현 방법 (Java)

import java.util.*;

public class Main {

    // 노드의 개수(V)와 간선(Union 연산)의 개수(E)
    // 노드의 개수는 최대 100,000개라고 가정
    public static int v, e;
    public static int[] parent = new int[100001]; // 부모 테이블 초기화하기

    // 특정 원소가 속한 집합을 찾기
    public static int findParent(int x) {
        // 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
        if (x == parent[x]) return x;
        return findParent(parent[x]);
    }

    // 두 원소가 속한 집합을 합치기
    public static void unionParent(int a, int b) {
        a = findParent(a);
        b = findParent(b);
        if (a < b) parent[b] = a;
        else parent[a] = b;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        v = sc.nextInt();
        e = sc.nextInt();

        // 부모 테이블상에서, 부모를 자기 자신으로 초기화
        for (int i = 1; i <= v; i++) {
            parent[i] = i;
        }

        // Union 연산을 각각 수행
        for (int i = 0; i < e; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            unionParent(a, b);
        }

        // 각 원소가 속한 집합 출력하기
        System.out.print("각 원소가 속한 집합: ");
        for (int i = 1; i <= v; i++) {
            System.out.print(findParent(i) + " ");
        }
        System.out.println();

        // 부모 테이블 내용 출력하기
        System.out.print("부모 테이블: ");
        for (int i = 1; i <= v; i++) {
            System.out.print(parent[i] + " ");
        }
        System.out.println();
    }
}

5. 서로소 집합 자료구조: 기본적인 구현 방법의 문제점

합집합(Union) 연산이 편향되게 이루어지는 경우 찾기(Find) 함수가 비효율적으로 동작합니다.
최악의 경우에는 찾기(Find) 함수가 모든 노드를 다 확인하게 되어 시간 복잡도가 O(V) 입니다.
- 다음과 같이 {1, 2, 3, 4, 5}의 총 5개의 원소가 존재하는 상황을 확인해 봅시다.

수행된 연산들: 𝑈𝑛𝑖𝑜𝑛(4,5), 𝑈𝑛𝑖𝑜𝑛(3,4), 𝑈𝑛𝑖𝑜𝑛(2,3), 𝑈𝑛𝑖𝑜𝑛(1,2)

서로소 집합 자료구조: 경로 압축

찾기(Find) 함수를 최적화하기 위한 방법으로 경로 압축(Path Compression)을 이용할 수 있습니다.
- 찾기(Find) 함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 바로 갱신합니다.

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if paret[x] != x:
    	parent[x] = find_parent(parent, parent[x])
    return parent[x]

경로 압축 기법을 적용하면 각 노드에 대하여 찾기(Find) 함수를 호출한 이후에 해당 노드의 루트 노드가 바로 부모 노드가 됩니다.
동일한 예시에 대해서 모든 합집합(Union) 함수를 처리한 후 각 원소에 대하여 찾기(Find) 함수를 수행하면 다음과 같이 부모 테이블이 갱신됩니다.
기본적인 방법에 비하여 시간 복잡도가 개선됩니다.

1. 서로소 집합 자료구조: 경로 압축 (코드)

1) 서로소 집합 자료구조: 경로 압축 (Python)

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화하기

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

# Union 연산을 각각 수행
for i in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)

# 각 원소가 속한 집합 출력하기
print('각 원소가 속한 집합: ', end='')
for i in range(1, v + 1):
    print(find_parent(parent, i), end=' ')

print()

# 부모 테이블 내용 출력하기
print('부모 테이블: ', end='')
for i in range(1, v + 1):
    print(parent[i], end=' ')

2) 서로소 집합 자료구조: 경로 압축 (Java)

import java.util.*;

public class Main {

    // 노드의 개수(V)와 간선(Union 연산)의 개수(E)
    // 노드의 개수는 최대 100,000개라고 가정
    public static int v, e;
    public static int[] parent = new int[100001]; // 부모 테이블 초기화하기

    // 특정 원소가 속한 집합을 찾기
    public static int findParent(int x) {
        // 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
        if (x == parent[x]) return x;
        return parent[x] = findParent(parent[x]);
    }

    // 두 원소가 속한 집합을 합치기
    public static void unionParent(int a, int b) {
        a = findParent(a);
        b = findParent(b);
        if (a < b) parent[b] = a;
        else parent[a] = b;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        v = sc.nextInt();
        e = sc.nextInt();

        // 부모 테이블상에서, 부모를 자기 자신으로 초기화
        for (int i = 1; i <= v; i++) {
            parent[i] = i;
        }

        // Union 연산을 각각 수행
        for (int i = 0; i < e; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            unionParent(a, b);
        }

        // 각 원소가 속한 집합 출력하기
        System.out.print("각 원소가 속한 집합: ");
        for (int i = 1; i <= v; i++) {
            System.out.print(findParent(i) + " ");
        }
        System.out.println();

        // 부모 테이블 내용 출력하기
        System.out.print("부모 테이블: ");
        for (int i = 1; i <= v; i++) {
            System.out.print(parent[i] + " ");
        }
        System.out.println();
    }
}

https://bu119.tistory.com/74

[알고리즘] 서로소 집합 (Disjoint Sets) - 사이클 판별

서로소 집합을 활용한 사이클 판별 서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있습니다. 참고로 방향 그래프에서의 사이클 여부는 DFS를 이용하여 판별할 수 있습니

bu119.tistory.com

참고 자료

https://freedeveloper.tistory.com/387

https://chae-data.tistory.com/15

https://velog.io/@yeahxne/%EC%9D%B4%EC%BD%94%ED%85%8C-2021-16.-%EC%84%9C%EB%A1%9C%EC%86%8C-%EC%A7%91%ED%95%A9-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0

https://www.youtube.com/watch?v=aOhhNFTIeFI&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=8

728x90

저작자표시

'Algorithm' 카테고리의 다른 글

[알고리즘] 크루스칼 알고리즘 (Kruskal Algorithm) (0)	2023.12.14
[알고리즘] 서로소 집합 (Disjoint Sets) - 사이클 판별 (0)	2023.12.10
[알고리즘] 최장 증가 부분 수열(LIS) 알고리즘 (0)	2023.09.01
[알고리즘] 에라토스테네스의 체 (소수 판별) (0)	2023.08.25
[알고리즘] 이진 탐색 / 이분 탐색 (Binary Search) (0)	2023.08.17

현재글[알고리즘] 서로소 집합 (Disjoint Sets) - 자료구조

250x250

Chadoll

Backend developer 👩‍💻

Baekjoon, API Gateway, cs, 골드, 그래프 탐색, 구현, Python, MSA 구축하기, MircroService, Algorithm, 백준, network, Project, Spring Cloud Gateway, 알고리즘, Spring Cloud, 파이썬, Architecture, spring boot, MSA,

Today :
Yesterday :

Chadoll