[알고리즘][자바]서로소 집합, Union Find

서로소 집합(Disjoint Sets)이란?

 

 

서로소 집합(Disjoint Sets)란 공통 원소가 없는 두 집합을 의미 합니다.
ex) {1,2}와 {3,4}는 서로소 관계이다
      {1,2}와 {2,3}은 서로소 관계가 아니다.

서로소 집합 자료구조

• 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조입니다.
• 서로소 집합 자료구조는 두 종류의 연산을 지원합니다.
  • 합집합(Union): 두개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산입니다.
  • 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산입니다.
• 서로소 집합 자료구조는 합치기 찾기(Union Find)자료구조라고 불리기도 합니다
• 여러 개의 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작 과정은 다음과 같습니다.
  1. 합집합(Union) 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인합니다.
     • A와 B의 루트 노드 A,B를 각각 찾습니다.
     • A를 B의 부모 노드로 설정합니다.
  2. 모든 합집합(Union) 연산을 처리할 때까지 1번의 과정을 반복합니다.

기본적인 구현 방법의 문제점

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

경로 압축

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

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

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

//서로소 집합
public class Main {
	static int[] parent;
	public static void main(String[] args) {
		//10개 정도의 집합이 있어서 그집합을 서로소집합으로 관리하기
		parent = new int[10 + 1];
		makeSet();
		
//		System.out.println(findSet(2));
//		System.out.println(findSet(5));
		union(2,5);
		union(4,7);
		System.out.println(findSet(2));
		System.out.println(findSet(7));
		union(2,7);
		System.out.println(findSet(2));
		System.out.println(findSet(7));
		for(int i =1;i<11;i++) {
			
			System.out.print(parent[i] + " ");
		}
	}
	static void union(int x, int y) {
		x = findSet(x);
		y = findSet(y);
		if( x == y) {
			return;
		}
		parent[y] = x;
	}
	
	static int findSet(int x) {
		if(x == parent[x]) {			
			return x;
		}		
		return parent[x] = findSet(parent[x]);
		
		//int px =findSet(parent[x]);
		//parent[x] = px;
		//return px;
	}
	static void makeSet() {
		for(int i =1 ;i<parent.length; i++) {
			parent[i] = i;
		}
	}
}

 

사이클 판별

• 서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있습니다.
  • 참고로 방향 그래프에서의 사이클 여부는 DFS를 이용하여 판별할 수 있습니다.
• 사이클 판별 알고리즘은 다음과 같습니다.
  1. 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인합니다.
     1. 루트 노드가 서로 다르다면 두 노드에 대하여 합집합(Union) 연산을 수행합니다.
     2. 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것입니다.
  2. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복합니다.

import java.util.Scanner;

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);
		boolean cycle = false;//사이클 발생 여부
		
		for(int i =0 ;i<e;i++) {
			int a = sc.nextInt(); 
			int b = sc.nextInt();
			
			//사이클이 발생한 경우 종료
			if(findParent(a) == findParent(b)) {
				cycle = true;
				break;
			}
			//사이클이 발생하지 않았다면 합집합(Union) 연산 수행
			else {
				unionParent(a,b);				
			}
		}
		if(cycle) {
			System.out.println("사이클이 발생했습니다.");
		}else {
			System.out.println("사이클이 발생하지 않았습니다.");
		}
			
	}
}

 

 

참고