[Algorithm] 유니온 파인드 / Union-Find

1. 유니온 파인드 알고리즘이란?

• 대표적인 그래프 알고리즘으로 두개의 노드가 같은 집합에 속하는지 판별하는 알고리즘
• 서로소 집합 또는 상호배타적 집합(Disjoint-Set) 알고리즘이라고도 불린다
• 노드를 합치는 Union연산과 루트 노드를 찾는 Find연산으로 이루어져있다.
• 시간복잡도는 트리의 높이만큼 탐색하는 O(logN)을 가지게 된다. Union을 해주는 과정에서 한쪽으로만 노드들이 달리는 사향트리의 형태를 띄게 되면 O(n)이 되어버린다. 

---

2. Default Logic

 

현재 7개의 서로 관련이 없는 노드가 존재하고 우리는 1, 2 / 4, 5 / 5, 6 노드를 서로  연결하려고 한다. 현재는 아무런 연관이 없기 때문에 각 노드들에 대한 root node는 자기 자신이다. 

 

1번 노드와 2번 노드를 연결하려면 2번 노드의 Root Node의 값을 코드상에서는 node[2]을 1로 변경해준다.

이번에는 4번 노드와 5번 노드를 연결해 줄 것이다. 이전과 똑같이 진행된다.

이번에는 5번과 6번을 이어 줄 것이다. 여기서 방법이 두가지로 갈린다.

1. 5번 노드에 6번을 잇는 경우 (인접한 부모노드에 연결)

2. 5번노드의 Root Node에 6번을 잇는 경우 (루트노드에 연결)

그림으로 먼저 보자면

 

1번 경우 :  인접한 부모노드에 연결(사향트리)

5번노드에 6번노드를 연결하게 되면 우리는 find함수로 루트노드를 찾을 때 재귀를 사용해서 찾기 때문에 지금이야 3개밖에 없어서 적어 보이지만 노드가 여러개 연결되게 되면 시간복잡도가 O(n)이 되게 된다. 그래서 우리는 단지 인접한 부모노드에 연결해주는게 아닌 각 노드의 뿌리노드를 찾아서 연결해 주어야 한다.  아래와 같이 4 > 5 > 6 쭉 연결된 것 처럼 모든 노드가 오른쪽이나 왼쪽으로 연결 된 트리구조를 사향 트리라고 한다. 2번 경우를 보자

2번 경우 : 루트노드에 연결

아래 그림처럼 부모노드의 루트노드에 연결하게 되면 트리의 편향 문제를 줄일 수 있으며 find하는데 걸리는 시간을 줄일 수 있어 좋은 방법이다.

 

#include<bits/stdc++.h>

using namespace std;

int node[9];

int find(int x) {
    if(node[x] == x)
        return x;
    
    return node[x] = find(node[x]);
}

void merge(int a, int b) {
    int x = find(a);
    int y = find(b);
    
    if(x == y) return;
    
    if(x != y) {
        //노드 값이 작은 쪽으로 붙도록 : 재귀 도는 시간 줄어듬
        if(x < y) node[y] = x;
        else node[x] = y;
    }
}

bool isUnion(int a, int b) {
    int x = find(a);
    int y = find(b);

    if(x == y) return true;
    else return false;
}

int main() {
	for (int i = 1; i <= 8; i++)
		node[i] = i;

	merge(1, 2);
	merge(4, 5);
	merge(5, 6);
	cout << "2와 4는 같은 집합인가?\n" << isUnion(2, 4) << "\n"; // false
	merge(1, 5);
	cout << "2와 4는 같은 집합인가?\n" << isUnion(2, 4) << "\n"; // true
	return 0;
}

---

3. 추천 문제

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

https://www.acmicpc.net/problem/1976

1976번: 여행 가자

 

https://www.acmicpc.net/problem/1043

1043번: 거짓말

---