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

https://github.com/csy-59/CodingTestPrac/tree/main/%EB%B0%B1%EC%A4%80/Gold/4195.%E2%80%85%EC%B9%9C%EA%B5%AC%E2%80%85%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC

CodingTestPrac/백준/Gold/4195. 친구 네트워크 at main · csy-59/CodingTestPrac

백준의 친구 네트워크 문제를 풀며 처음 접했던 알고리즘이다.

당시 모든 트리의 내용을 저장하지 않더라도, 해당 트리의 루트만 기억하면 된다는 점에서 신기했던 알고리즘이었다.

다음은 알고리즘에 대한 설명과 예제이다.

 

1. 알고리즘 개요

Union-Find는 서로소 집합(Disjoint Set)을 구현하기 위한 알고리즘이다.

서로소 집합은는 공통 원소가 없는 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다.

예시로 올려준 백준의 친구 네트워크 문제처럼, 같은 요소(친구, 인물)가 전체 집합에 모두 중복으로 포함될 수 없는 경우 사용될 수있다.

 

Union-Find 알고리즘은 해당 자료구조를 트리, 배열 등을 통해 구현하며, 각 요소가 어떤 집합에 소속되어 있는지를 해당 요소의 루트가 어디인지 확인하는 방식으로 빠르게 탐색할 수 있다.

 

2. 알고리즘의 핵심 연산

1) 집합 만들기

집합에 대한 초기화를 진행한다.

주어진 최대 요소 값을 기반으로 집합을 제작하고, 각 집합의 루트 노드 번호를 자기자신(혹은 경우에 따라 달라질 수 있음)으로 세팅한다.

class UnionFind {
public:
	vector<int> parent;
    
    UnionFind(int size)
    {
    	for(int i = 0; i< size; ++i)
        {
        	parent.push_back(i);
        }
    }
}

2) 요소 찾기

특정 요소가 속한 집합의 루트값을 반환한다.

이를 통해 해당 요소가 어떤 집합에 속해있는지 확인할 수 있으며, 압축 연산을 통해 이후에 더 빠르게 요소를 찾을 수 있도록 진행한다.

class UnionFind {
public:
	vector<int> parent;
    
    ...
    
    int Find(int x)
    {
    	if(parent[x] == x) return x;
        return parent[x] = Find(x); // 여기서 압축 진행
    }
}

 

3)  결합

특정 요소 2가지가 속한 집합을 합한다.

class UnionFind{
public:
	vector<int> parent;
    
    ...
    
    void Union(int x, int y)
    {
    	int xP = Find(x);
        int yP = Find(y);
        
        if(xP == yP) return;
        
        // 예시: 루트값은 더 작은 값으로 사용
        if(xP < yP) parent[y] = xP;
        else parent[x] = yP;
    }
}

3. 후기

새로운 알고리즘을 익힐 수 있어서 좋았다.

사실 친구 네트워크 문제를 풀 때도 무지성으로 unordered_set으로 접근했다가, 해당 알고리즘의 존제를 알게 되었다.

사실 코테 준비를 하면서 뭔가 알고리즘을 공부하는 것보다 문제를 많이 푸는게 중요하다 라고 생각을 했는데,

해당 알고리즘에 대해 공부하며, 다양한 알고리즘과 자료구조를 더 많이 공부해야겠다는 생각이들었다.

 

4. 참고 포스트

https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html?utm_source=chatgpt.com