Union-Find [c++]

 

Union-Find는 그래프 알고리즘으로써, '합집합 찾기'라는 의미를 가진다.

 

여러개의 연결되지 않은 노드 집합들이 있다고 가정하자.

 

(1) - (2) - (3) - (4)

(5) - (6) - (7) - (8)

 

1,2,3,4와 5,6,7,8을 각각 연결되어있는 노드들이다.

 

여러한 그래프에서 '연결성'을 프로그래밍 언어로 표현하는 것이 Union-Find 알고리즘이다.

 

Union-Find 알고리즘의 원리는

노드의 집합중 가장 작은 값을 가지는 노드가 부모 노드라고 가정하고,

ex) 1,2,3,4의 부모노드는 모두 1이다.

부모노드가 같으면 연결되어 있다고 생각하는 것이다.

 

find는 해당 노드의 부모 노드를 찾는 알고리즘이고

ex) find(3)을 하면 1을 반환

union은 노드의 집합을 연결하는 알고리즘이다.

 

이를 구현하기위해 parent 배열을 이용할 것이다.

ex) parent[3] = 2는 3번 노드의 부모는 2라는 뜻이다.

 

 

// Union-Find(Disjoint-set)

#include <iostream>

 

using namespace std;

 

// 부모 노드를 찾는 함수

int findParent(int parent[], int x) {

if(parent[x] == x) return x; // 부모가 자신일 경우

return findParent(parent, parent[x]);

}

 

// 두 부모 노드를 합치는 함수

int unionParent(int parent[], int a, int b) {

a = findParent(parent, a);

b = findParent(parent, b);

if(a < b) parent[b] = a;

else parent[a] = b;

}

int main() {

int parent[11];

for(int i=1; i < 11; i ++)

parent[i] = i;

 

unionParent(parent, 1, 2); // 1,2,3,4 연결

unionParent(parent, 2, 3);

unionParent(parent, 3, 4);

 

unionParent(parent, 5, 6); // 5,6,7,8 연결

unionParent(parent, 6, 7);

unionParent(parent, 7, 8);

 

unionParent(parent, 4, 5); // 4,5 연결(전부연결)

 

int s=2, k=8;

s = findParent(parent, s);

k = findParent(parent, k);

if(s == k) cout << "1" << endl; // 2와 8이 연결되있으면(부모노드 같으면) 1 출력

else cout << "0" << endl;

 

return 0;

}

 

 

 

cf ) https://bowbowbow.tistory.com/26