Algorithm 공부 #14 - 유니온 파인드(Union Find)

 

Algorithm 공부 #14 - 유니온 파인드

 

 

✏️ 유니온 파인드(Union Find)

유니온 파인드는 합집합이라는 의미를 지니고 있으며, Disjoint Set이라고도 불린다. Disjoint Set은 상호 베타적 집합이라는 뜻을 가지고 있는데 상호 배타적인 부분 집합들로 나누어진 원소들을 저장하고 조작하는데 사용한다.

상호 배타적이라는 단어가 헷갈릴 수 있는데, 그냥 부분 집합 간의 교집합에는 원소가 없고, 모든 부분 집합들의 합집합은 전체 집합과 같다는 뜻이다. 쉽게 말해서 여러 노드가 존재할 때 두개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하기 위해 사용한다고 생각하면 될 것 같다.

 

✏️ Union 연산

Union 연산은 말 그대로 Union(합집합)을 만드는 과정이다. 예를 들어서 두 노드가 있을 때 두 노드를 A와 B라고 하자

각 노드들은 어떤 집합에 속해있게 되는데 A와 B가 같은 집합에 있는지 없는지를 확인하고 같은 집합에 있다면

Union을 하지 않고, 다른 집합에 있다면 A와 B를 같은 집합으로 만들어준다. 

A와 B가 같은 집합에 있는지 없는지를 확인하는 함수는 find함수로 밑 부분에서 설명하겠다.

 

 

✏️ find 함수

위에서 잠깐 언급했었는데 Union 연산을 할 때 두 노드가 같은 집합에 있는지 검사해주는 함수이다.

그리고 검사를 하는 동시에 각 노드값들의 부모노드(위에서 언급한 집합인데 루트 노드라고 생각하면 될 것 같다)

를 갱신해준다. 모든 노드가 루트 노드에 직접 연결되면서 find속도가 빨라지고 경로 압축의 효과를 준다

이게 어떻게 되는지에 대해 의문을 가질 수도 있는데 find함수의 작동 원리를 한 번 살펴보자

 

find함수의 작동 원리

1. 대상 노드 배열의 index값과 value값이 동일한지 확인
2. 동일하다면 return을, 동일하지 않다면 value값이 가리키는 index값으로 이동
3. 이동 위치의 index값과 value값이 같을 때까지(대표 노드를 찾을 때까지)이동
4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 대표 노드값으로 변경

index는 각각의 노드이고 value값은 각 노드들의 부모노드이다.

그리고 여기서 사용하는 배열은 parent배열이고, parent배열은 시작 시 각 인덱스에 대해 parent[i]=i의 연산을 시행한다

1번 과정은 두 개의 노드의 부모 노드가 같은지(같은 집합체에 있는지) 확인하는 단계이다

2번 과정은 동일하다면(같은 집합체에 있다) Union연산을 할 필요가 없으므로 return해주고, 동일하지 않다면(같은 집합체에 있지 않다면) 노드가 가리키는 부모 노드로 이동하는 단계이다

3번 과정은 최종 부모 노드(루트 노드 또는 대표 노드라고 생각하자)를 찾을 때까지 이동하는 단계이다

4번 과정은 대표 노드에 도달한 상태이며 재귀 함수를 빠져나오면서 대표 노드에 오면서 거쳐왔던 모든 노드들의 대표 노드값을 변경해주는 단계이다.

 

시간 복잡도

 

경로 압축 최적화를 하지 않은 find 함수 시간 복잡도는 O(n)으로 선형 시간 복잡도를 가진다.

이때 경로 압축 최적화를 하게 되면, 시간 복잡도가 O(α(n))으로 바뀐다.

여기서 α(n)는 애커만 함수(Ackermann function)의 역함수인데, 우리가 상상할 수 있는 모든 크기의 n에 대해 4 이하의 값을 가진다고 한다. 즉, 경로 압축 최적화를 적용하면, 현실적으로 가능한 모든 n에 대해서 find 함수는 상수 시간 복잡도를 가진다는 말과 같다.

 

✏️ 동작 예시

먼저, 위와 같은 트리들이 있다고 가정하자

그러면 (1,2,5,6,8) / (3,4) / (7) 이렇게 총 3개의 집합체가 존재한다.

 

연산을 마친 후 트리들이 모두 연결된 모습이다.

만약 여기서 7의 대표 노드를 찾기 위해 find(7)를 하게 된다면?

 

이렇게 경로 압축이 된다

 

✏️ 코드로 구현하기

void Union(int a, int b) { // Union 함수
	int node1 = find(a);
	int node2 = find(b);

	if (node1 != node2) {
		parent[node2] = node1;
	}
}

int find(int node) { // find 함수
	if (parent[node] == node)
		return node;
	else
		return parent[node] = find(parent[node]);
}

 

 

✏️ 예시 문제

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

1717번: 집합의 표현

 

#include<iostream>
#include<vector>
using namespace std;

vector<int>A;
void Union(int a, int b);
int find(int a);
int node = -1;
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	cin >> n >> m;
	A.resize(n + 1);
	for (int i = 0; i <= n; i++)
		A[i] = i;

	for (int i = 0; i < m; i++) {
		int x;
		cin >> x;
		int a, b;
		cin >> a >> b;
		if (x == 0)
			Union(a, b);
		else if (x == 1) {
			int in1 = find(a);
			int in2 = find(b);
			if (in1 == in2)
				cout << "YES" << '\n';
			else
				cout << "NO" << '\n';
		}

	}
}
void Union(int a, int b) {
	int MAX = max(a, b);
	int MIN = min(a, b);

	if (A[a] == a && A[b] == b) { //둘 다 아무런 노드와 연결이 되어 있지 않다면
		A[MAX] = MIN; // 더 작은 값을 대표 노드로 설정
	}

	else { // 그게 아니라면 둘다 대표 노드값을 찾기
		int node1 = find(a); //a의 대표노드
		int node2 = find(b); //b의 대표노드
		int MAX1 = max(node1, node2);
		int MIN1 = min(node1, node2);
		A[MAX1] = MIN1; // 더 작은 값을 대표노드로
	}
}
int find(int a) {
	if (a == A[a])
		return a;
	return A[a] = find(A[a]);
}

 

 

 

✏️ 예시 문제 2

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

1976번: 여행 가자

 

#include<iostream>
#include<vector>
using namespace std;
vector<int>parent;

void Union(int a, int b);
int find(int a);

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N,M;
	cin >> N>>M;
	int A[201][201];

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> A[i][j]; // 정보 입력받기
		}
	}

	int travel[1001];
	for (int i = 1; i <= M; i++) {
		cin >> travel[i];
	}

	parent.resize(N + 1);
	for (int i = 0; i <= N; i++)
		parent[i] = i; // 초기 배열 설정
	
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (A[i][j] == 1)
				Union(i, j);
		}
	}
	
	int res = find(travel[1]);
	bool check = true;

	for (int i = 2; i <= M; i++) {
		int node = find(travel[i]);
		if (node != res) {
			check = false;
			break;
		}
	}

	if (check)
		cout << "YES";
	else
		cout << "NO";
}

void Union(int a, int b) {
	int node1 = find(a);
	int node2 = find(b);

	if (node1 != node2)
		parent[node2] = node1;
}

int find(int a) {
	if (parent[a] == a)
		return a;
	else
		return parent[a] = find(parent[a]);
}

 

 

 

✏️ 예시 문제 3

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

1043번: 거짓말

 

 parent배열, 파티를 저장할 배열(2차원), 진실을 아는 사람을 배열(truep)을 각각 생성

 먼저 파티들을 전부 union하고 각각의 일차원 배열들의 첫번째 값을 대표노드로 설정하기

그 다음 M개만큼 반복문을 돌려서 cur에 party[i][0]값을 저장하고 find(cur)이 truep에 존재한다면 

check=false로 바꾸고 반복문 종료, 존재하지 않는다면 결괏값+1

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
static  vector<int> parent;
static  vector<int> trueP;
static vector < vector <int> > party;
static int result;

void unionfunc(int a, int b);
int find(int a);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M, T;
    cin >> N >> M >> T;
    trueP.resize(T);
    for (int i = 0; i < T; i++) { // 진실을 아는 사람 저장
        cin >> trueP[i];
    }
    
    party.resize(M);

    for (int i = 0; i < M; i++) { // 파티 데이터 저장
        int party_size;
        cin >> party_size;
        for (int j = 0; j < party_size; j++) {
            int temp;
            cin >> temp;
            party[i].push_back(temp);
        }
    }

    parent.resize(N + 1);
    for (int i = 0; i <= N; i++) { // 대표 노드를 자기 자신으로 초기화 하기
        parent[i] = i;
    }

    for (int i = 0; i < M; i++) { // 각 파티에 참여한 사람들을 하나의 그룹으로 만들기 -> union 연산
        int firstPeople = party[i][0];
        for (int j = 1; j < party[i].size(); j++) {
            unionfunc(firstPeople, party[i][j]);
        }
    }
    for (int i = 0; i < M; i++) { // 각 파티에서 진실을 아는 사람과 같은 그룹에 있다면 과장 할 수 없음
        bool isPossible = true;
        int cur = party[i][0];
        for (int j = 0; j < T; j++) {
            if (find(cur) == find(trueP[j])) {
                isPossible = false;
                break;
            }
        }
        if (isPossible)
            result++;
    }
    cout << result;
}
void unionfunc(int a, int b) { // union 연산 : 바로 연결이 아닌 대표 노드끼리 연결하여 줌
    a = find(a);
    b = find(b);
    if (a != b) {
        parent[b] = a;
    }
}
int find(int a) { // find 연산
    if (a == parent[a])
        return a;
    else
        return parent[a] = find(parent[a]); // 재귀함수의 형태로 구현
}