[Algorithm] 서로소 집합 자료구조

서로소 집합은 공통 원소가 없는 두 집합을 의미한다.

서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조다.

연산

서로소 집합 자료구조는 union과 find 2개의 연산으로 조작할 수 있다.

union 연산은 2개의 원소가 포함된 집합을 하나로 합치는 연산이고,

find 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다.

서로소 집합 자료구조

서로소 집합 자료구조에서 집합을 표현하는 서로소 집합 계산 알고리즘은 다음과 같다.

 

1. union 연산을 확인해, 서로 연결된 두 노드 A, B를 확인한다.

 A와 B의 루트 노드 A'와 B'를 찾는다. A'를 B'의 부모 노드로 설정한다.

2. 모든 union 연산을 처리할 때까지 1번 과정을 반복한다.

 

일반적으로 트리 자료구조를 이용해 표현하기 때문에, A'와 B' 중 더 작은 번호가 부모 노드가 되도록 구현하는 경우가 많다. 

 

전체 집합이 6개의 원소로 구성되어 있는 상황에, 4개의 union 연산이 주어진다면,

이는 그래프의 형태로 생각할 수 있다. 6개의 노드와 4개의 간선으로 생각할 수 있다.

서로소 집합 자료구조

부모노드 테이블

소스코드로 표현하면 다음과 같다.

import java.util.*;

class Main {

  public static int n, m;
  public static int[] parentNode = new int[30001]; //부모 노드 정보 저장

  public static int findParent(int x) { //부모노드를 찾는다.
    if (parentNode[x] != x) { //본인이 부모 노드가 아니라면 
      return findParent(parentNode[x]); //재귀적 호출로 부모 노드를 찾는다.
    }
    return x;
  }

  public static void unionParent(int a, int b) {
    a = parentNode[a]; // a의 부모노드
    b = parentNode[b]; // b의 부모노드
    if (a < b) { //더 작은 값이
      parentNode[b] = a; // 부모가 된다.
    } else {
      parentNode[a] = b;
    }
  }

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    m = sc.nextInt();

    // 부모노드 초기화
    for (int i = 0; i <= n; i++) {
      parentNode[i] = i;
    }

    for (int i = 0; i < m; i++) {
      int a = sc.nextInt();
      int b = sc.nextInt();
      unionParent(a, b);
    }

    for (int i = 1; i <=n; i++) {
      System.out.print(findParent(i) + " ");
    }

    System.out.println();

    for (int i = 1; i <=n; i++) {
      System.out.print(parentNode[i] + " ");
    }
    
  } // end main
}

 

먼저, 부모 노드를 찾는 메서드는 해당 노드가 어떤 집합에 속했는지 확인하기 위함이다.

더 작은 값은 부모 노드로 사용하는 트리구조로 되어 있기 때문에, Union 연산 결과는 더 작은 부모를 가진 것에 다른 집합을 붙이도록 연산한다.

 

하지만, 위와 같은 소스코드로 연산할 경우 부모노드를 찾는데 최악의 경우 모든 노드를 다 확인해야 하기 때문에 비효율적인 연산이 된다. 경로 압축 기법을 적용하면 개선시킬 수 있다. 경로 압축은 find 메서드를 재귀적으로 호출한 뒤에 부모 테이블 값을 갱신하는 기법이다.

  public static int findParent(int x) {
    if (parentNode[x] != x) { 
      parentNode[x] = findParent(parentNode[x]);
    }
    return parentNode[x];
  }

이렇게 진행될 경우, 부모 노드 테이블에 변화가 생긴다.

개선된 서로소 집합 자료구조 부모노드 테이블

루트 노드에 더욱 빠르게 접근할 수 있다는 점에서 시간 복잡도가 개선된다.

언제 사용하는가?

서로소 집합 자료구조를 사용하면 무방향 그래프 내에 사이클이 발생하는지 확인할 수 있다.

3개의 노드가 있을 때,  각각 Union 연산을 간선으로 표현하면서 하나의 그래프를 구성한다고 가정하자.

Union 1, 2에서 1과 2는 부모노드가 1을 가리킨다.

Union 1, 3에서 1과 3은 부모노드가 1을 가리킨다.

Union 2, 3에서 이미 2와 3은 부모노드 1을 가리키고 있다. 그렇다는 것은 1-2 간선과 1-3 간선이 존재하는데,

2-3 간선이 생긴다는 것으로 사이클이 생긴다는 것을 판별하게 된다.