[Week10] Union Find 알고리즘 (java)

 

Union-Find 알고리즘이란?

서로소 집합(Disjoint-Set) 알고리즘이라고도 불리는 알고리즘

여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘

 

Disjoint-Set (서로소 집합)?
서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
즉, 공통 원소가 없는 부분 집합들로 나눠진 원소들에 대한 자료구조

 

Union-Find 알고리즘의 과정

초기화 (makeSet) - 합치기 (union) - 찾기 (find) 연산 과정을 거친다

 

1. 초기화 (makeSet)

union과 find 연산을 하기전, 각 노드를 하나의 집합으로 초기화하는 과정

자기 자신이 가리키는 대상 = 자신이 속한 집합이 되기 때문에, 자기 자신이 가리키는 대상을 부모라고 표현한다. 

초기 원소는 자기 자신의 번호를 자신이 속한 집합이라고 인식한다. 

ex) 1 ~ 5 노드가 있을 때 {1}, {2}, {3}, {4}, {5} 처럼 하나의 유일한 노드를 가지는 집합으로 만든다.

import java.util.Arrays;

public class DisjointSet {
	public static void main(String[] args) {
		int[] parent = MakeSet(5);
		// 각 인덱스(=노드)는 자기 자신을 가리키고 있다
		System.out.println(Arrays.toString(parent));
	}

	private static int[] MakeSet(int size) {
		// 각 인덱스에 번호가 대응하도록 사이즈를 1더하여 배열 선언.
		int[] arr = new int[size + 1];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = i;
		}
		return arr;
	}
}

 

2. 합치기(union)

두 집합을 합치는 과정

서로 다른 두 원소를 같은 집합으로 포함시키기 위해서는 두 원소가 모두 같은 부모를 가리키도록 값을 변경해주면 된다. 

이 경우 보통 두 원소중 작은 값을 기준으로 가리키는 부모를 통일 시켜준다. 

ex) 위의 예시에서 1과 2번 노드를 합친다면 {1, 2}, {3}, {4}, {5} 처럼 집합이 합해져 하나의 집합이 된다.

private static void union(int[] parent, int a, int b) {
		// 각 집합을 대표하는 부모가 다른 부모로 편입 되어야 한다. 원소가 편입되어서는 안된다.
		a = find(parent, a);
		b = find(parent, b);
		if (a > b) {
			parent[a] = b;
		} else {
			parent[b] = a;
		}
	}

 

3. 찾기(find)주어진 노드가 속한 집합의 대표 노드를 반환

이때, 각 집합은 대표 원소(또는 부모 노드)를 가지며, 이를 통해 집합 간의 관계를 파악한다. 

private static int find(int[] parent, int x) {
		// 만일, 찾는 대상과 인덱스 번호가 같다면 그 인덱스(=노드)가 해당 집합의 부모이다.
		if (parent[x] == x)
			return x;
		// 그렇지 않다면, 해당 인덱스가 가리키는 값(부모 노드)을 따라 최종 부모노드까지 탐색한다.
		else
			return find(parent, parent[x]);
	}

집합은 어떤 자료구조로 구현하는게 좋을까?
보통 트리 구조로 구현되며, 각 노드는 자신의 부모를 가리키는 포인터를 가진다. 
여러 원소들을 포함하는 집합을 표현하기 위해 트리의 루트 노드가 해당 집합의 대표 원소로 선택된다. 

 

예시

1부터 6까지 노드가 있을 때, 5개의 union 연산 [union(1, 4), union(2,3), union(2,4), union(5,6)] 이 주어진 상태

 

초기 상태

 

union 후 상태

 

1. 부모 테이블 초기화
노드의 개수 크기의 부모 테이블을 초기화 한다. 초기값은 자기 자신을 부모로 가지도록 설정한다.

노드번호	1	2	3	4	5	6
부모	1	2	3	4	5	6

 

2. union 연산

2-1 union(1,4)

현재 루트 노드는 각각 1과 4이므로 더 큰 번호인 루트 노드 4의 부모를 1로 설정

노드번호	1	2	3	4	5	6
부모	1	2	3	1	5	6

 

2-2 union(2,3)

현재 루트 노드는 각각 2와 3이므로 더 큰 번호인 루트 노드 3의 부모를 2로 설정

노드번호	1	2	3	4	5	6
부모	1	2	2	1	5	6

 

2-3 union(1, 2)

현재 루트 노드는 각각 1와 2이므로 더 큰 번호인 루트 노드 2의 부모를 1로 설정

노드번호	1	2	3	4	5	6
부모	1	1	2	1	5	6

 

2-4 union(5,6)

현재 루트 노드는 각각 5와 6이므로 더 큰 번호인 루트 노드 6의 부모를 5로 설정

노드번호	1	2	3	4	5	6
부모	1	1	2	1	5	5

 

union을 마친 상황

1과 3은 부모노드가 다른데 같은 집합인지 어떻게 확인?
재귀함수를 사용해서 알 수 있다. 3의 부모를 찾기 위해서는 먼저 3이 가리키고 있는 2를 찾고 2의 부모를 확인한다.
그러면 2의 부모가 1을 가리키고 있으므로 그제서야 결과적으로 3은 1과 같은 집합이라는 것을 알 수 있다.

 

 

코드

public class Main {
	static int[] parent;

	// union 연산
	public static boolean union(int x, int y) {
		x = find(x);
		y = find(y);
		
		if(x == y) return false;
		
		if(x <= y) parent[y] = x;
		else parent[x] = y;
		return true;
	}
	
    // find 연산
	public static int find(int x) {
		if(parent[x] == x) return x;
		return find(parent[x]);
	}
    
     // parent 출력
	public static void parentPrint() {
		System.out.print("[ ");
		for (int i = 1; i < parent.length; i++) {
			System.out.print(parent[i]+ " ");
		}
		System.out.println("]");
	}

	public static void main(String[] args) {
		int n = 5;
		parent = new int[n + 1];
        // 부모 노드 초기화
		for (int i = 0; i < parent.length; i++) parent[i] = i;
		
        //위의 예제 실행
		union(1, 2);
		parentPrint();
		union(3, 4);
		parentPrint();
		union(3, 5);
		parentPrint();
		System.out.println("find(2): " + find(2));
		System.out.println("find(4): " + find(4));
		union(2, 4);
		parentPrint();
		System.out.println("find(4): " + find(4));
	}
}

 

 

 

 

https://velog.io/@ywc8851/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Union-Find-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[알고리즘] Union-Find 알고리즘

https://sskl660.tistory.com/71?category=845232

[Java]서로소 집합(Disjoint Set)(Union-Find)(Merge-Find Set)