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

Union-Find 알고리즘이란?

: 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지(같은 부모를 가지고 있는지) 판별하는 알고리즘 ('합집합 찾기'라는 의미를 가짐.)

✍️ 탐색 과정

1) 여러 개의 노드가 서로 자유분방하게 존재한다고 할 때, 이는 각자 자기 자신만을 원소로 가지고 있는 그래프라고 할 수 있다. 이 때 각 노드가 포함된 그래프의 부모를 표로 표현하면 아래와 같이 자기 자신을 가리키게 된다.

2) 1과 2가 연결되었다고 하면, 1과 2는 같은 그래프에 속해있게 되고, 2의 부모는 1이 된다. (부모를 합칠 때는 일반적으로 값이 더 작은 쪽으로 합침.) 이것을 Union(합침)이라고 한다.

3) 2와 3도 연결되었다고 하면, 3의 부모는 먼저 2가 된다. 하지만 최종적으로는 1이 되어야 하므로, 이 때 재귀함수가 사용된다. 3의 부모를 찾기 위해서는 먼저 3이 가리키고 있는 2를 찾고, 그 이후 2가 가리키고 있는 1을 찾는 것이다. 1과 같이 자기 자신을 가리키고 있는 경우에 재귀함수를 종료한다. 맨 아래 표와 같이 1, 2, 3은 모두 1을 가리키게 되므로 1, 2, 3은 같은 그래프에 속해있는 것이다.

🖥️ 코드 구현

// x 노드의 부모 반환
int getParent(int parent[], int x)
{
	if (parent[x] == x) return x;
	return parent[x] = getParent(parent, parent[x]);
}

// a 노드와 b 노드의 부모를 합침
void unionParent(int parent[], int a, int b)
{
	a = getParent(parent, a);
	b = getParent(parent, b);

	// 더 작은 쪽으로 부모를 합침.
	if (a < b) parent[b] = a;
	else parent[a] = b;
}

// a 노드와 b 노드가 같은 부모 가지고 있는지(같은 그래프에 속해있는지) 확인
int findParent(int parent[], int a, int b)
{
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a == b) return 1;
	else return 0;
}

int main()
{
	int parent[11];

	// 노드 0 ~ 10이 각자 자기 자신을 부모로 가리키게 함.
	for (int i = 0; i <= 10; i++)
		parent[i] = i;

	unionParent(parent, 1, 2);
	unionParent(parent, 2, 3);
	unionParent(parent, 3, 4);
	unionParent(parent, 4, 5);
	unionParent(parent, 5, 6);
	unionParent(parent, 6, 7);

	cout << "1과 8 연결 여부 : " << (findParent(parent, 1, 8) ? "연결됨." : "연결 안 됨.") << endl;
	cout << "1과 3 연결 여부 : " << (findParent(parent, 1, 3) ? "연결됨." : "연결 안 됨.") << endl;

	return 0;
}

// 실행 결과 : 1과 8 연결 여부 : 연결 안 됨.
		      1과 3 연결 여부 : 연결됨.

👁️‍🗨️ 참고
https://m.blog.naver.com/ndb796/221230967614
https://youtu.be/AMByrd53PHM