Union / Find Algorithm

 Union / Find 알고리즘이란?

---

 -> 그래프 알고리즘 중 하나로 합집합을 찾는 방법.

 -> 상호 배타적 집합(Disjoint-Set)이라고도 함.

 -> 여러 노드(정점)가 주어질 때, 두 개의 노드(정점)를 선택해서 현재 두 노드(정점)가 서로 같은 그래프에 속하는지 판별하는 알고리즘.

 -> Find : x가 어떤 집합에 포함되어 있는지 찾는 연산

 -> Union : x와 y가 포함되어 있는 집합을 합치는 연산

 -> 처음에는 모든 노드의 부모를 해당 인덱스(자기 자신)로 설정

 

샘플 코드

---

  - Union 함수

// 두 노드를 합치는 함수
	public static void union(int x, int y) {
		x = find(x);
		y = find(y);
		if(x != y)
			parent[y] = x;
	}

 

 - Find 함수

// 부모 노드를 찾는 함수
	public static int find(int index) {
		if(parent[index] == index) {
			return index;
		}
		return parent[index] = find(parent[index]);	// 부모의 부모를 탐색해서 parent를 변경시키고 리턴
	}

 

 - 두 노드의 부모를 찾는 함수

// 두 노드의 부모 노드가 일치하는지 찾는 함수
	public static boolean isSameParent(int x, int y) {
		x = find(x);
		y = find(y);
		return x == y ? true : false;
	}

 

 

이상입니다.

 

감사합니다!