Union Find (유니온 파인드)

• 그래프 (트리) 알고리즘으로 두 노드가 같은 그래프에 속해있는지 판별
• Union 연산 & Find 연산
  • union(x, y) : 노드를 합치는 연산
  • find(x) : x가 어느 그래프에 속해 있는지 판별하는 연산 (노드의 루트 노드 탐색)

 

🕹️ 유니온 파인드 과정

현재 5개의 노드는 서로 연결되어있지 않은 상태이므로 부모는 자기 자신을 가리키고 있다. (부모 노드 초기화)

x는 노드 번호이고, parent[x]는 x가 어떤 부모 노드에 속해 있는지 나타낸다. 

 

 

1️⃣ union(1, 2)

 

노드 1과 노드 2를 합친다. 노드 2의 부모 노드는 1이 되었다. parent[2] = 1

 

2️⃣ union(3, 4) /  union(3, 5)

 

노드 3과 노드 4를 합치고, 노드 3과 노드 5를 합친다.
노드 4와 노드 5의 부모는 모두 노드 3이 되었다. parent[3] = 3, parent[4] = 3, parent[5] = 3

부모를 합칠 때는 일반적으로 더 작은 값 쪽으로 합친다.

노드 2와 4의 부모 노드는 find 연산으로 찾을 수 있다. find(2) = 1, find(4) =3

 

 

3️⃣ union(2, 4)

 

노드 2가 속한 그래프와 노드 4가 속한 그래프를 합친다. 

1과 4의 부모가 다르기 때문에 복잡한 그래프 속에서는 '1과 4가 연결되었다'는 것을 파악하기 어려울 수 있다. 

이때 재귀함수를 사용해서 4의 부모인 3을 먼저 찾은 후, 3의 부모인 1을 찾아서 결과적으로 4의 부모가 1인 것을 확인해 서로 연결되었음을 파악할 수 있다. 

find(3)=1, find(4)=1

 

---

 

유니온 파인드 코드  구현

 

union 연산

public static boolean union(int x, int y) {
	x = find(x); //x의 부모노드 찾기
	y = find(y); //y의 부모노드 찾기
    
	// 이미 같은 그래프에 속해있을 때 false 반환
	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 parent[x]=find(parent[x]);
}