[알고리즘/C++] - Union Find 알고리즘 (1043-거짓말)

제 유니온은 3000찌끄레기입니다

안녕하세요
오늘도 새로운 알고리즘을 알아내서 공유하러 왔도다
그것은 바로 Union-Find 알고리즘입니다.
사실 이 알고리즘은 "그냥풀이법인데 괜히 고상하게 알고리즘이라고 이름붙인거아닌가"라고 생각되는 대표적인 알고리즘입니다!ㅋ
왜냐면 개인적으로 봤을 때 응용도가 많이 낮다고 생각되기 때문입니다..
그래도 알아두면 언젠가는 쓸모있지 않을까 싶어 일단은 정리해두려고 합니다

---

Union Find

: 서로 다른 두개의 집합을 하나로 병합하는 Union연산과, 하나의 원소가 어떤 집합에 속하는지를 판단하는 Find연산 을 활용하여 상호배타적 집합을 효율적으로 표현하기 위해 만들어진 자료구조.
 
말이 쉬우면서도 어려워보이는데, 내용은 간단합니다.
 
1. 각각의 원소들에 루트(부모)를 지정합니다. 처음 지정된 루트는 자기 자신입니다.
2. 연결하고자 하는 원소쌍을 선택합니다. a,b
3. 각 2개의 원소 a,b의 루트를 찾습니다.
4. 만약, 2개의 원소의 루트가 서로 같다면,
    4-1. 서로 결합된 상태이므로 넘기고,
    3-2. 아니라면, 결합되지 않았기 때문에, 원소 a의 루트를 다른 원소 b의 루트와 동일하도록 변경합니다.
4. 위 과정을 반복하여 최종적으로 결합된 하나의 자료구조를 완성시킵니다.
 

제가 열심히 만들어본 3컷만화입니다.
 
 
아래는 Union-Find의 대표적인 예를 C++로 구현한 버전입니다.

#include <iostream>
using namespace std;

int parent[1001]; // 부모 노드 저장용 배열

// 루트(대표) 찾기
int find(int x) {
    if (parent[x] == x) return x;      // 자기 자신이 루트면 반환
    return parent[x] = find(parent[x]); // 경로 압축
}

// 두 집합 합치기
void unionSet(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) parent[b] = a; // 루트가 다르면 병합
}

int main() {
    int n = 6; // 예시: 노드 1~6

    // 초기화
    for (int i = 1; i <= n; i++)
        parent[i] = i;

    // 집합 병합 예시
    unionSet(1, 2);
    unionSet(2, 3);
    unionSet(4, 5);

    return 0;
}

코드를 보면 2 Union-Find함수 하나 자체가 있는게 아닌, UnionSet, Find가 따로 있는 것을 알 수 있습니다.

    // 초기화
    for (int i = 1; i <= n; i++)
        parent[i] = i;

기본적으로 자기 자신을 먼저 루트로 가질 수 있도록 설정합니다.

// 루트(대표) 찾기
int find(int x) {
    if (parent[x] == x) return x;      // 자기 자신이 루트면 반환
    return parent[x] = find(parent[x]); // 경로 압축
}

여기서 원소 x에 대한 루트(부모)를 찾습니다. 계속해서 상위 노드를 거슬러 올라가면서 최종적으로 자기자신을 루트로 하는 원소를 찾아내면, 그 원소가 바로 x에 대한 루트입니다. 
계속적으로 본인의 상위노드를 거슬러 올라가는 원리로 인해 이 함수는 재귀를 활용하여 구현된 것을 볼 수 있습니다.

// 두 집합 합치기
void unionSet(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) parent[b] = a; // 루트가 다르면 병합
}

결합 작업을 진행합니다. 각각의 원소 a,b에 대한 루트를 찾고, 이 루트가 다른 경우, b의 루트를 a의 루트로 변경하여 결합합니다.

---

문제풀이

https://www.acmicpc.net/problem/1043
제가 만났던 문제를 공유합니다.

 
그짓말. 그짓말치면안되죠?
 
최대한 그짓말을 치고싶은 지민이가 그짓말을 칠수있는 파티의 개수를 알아보는 문제입니다.
진실을 아는 자들이 섞여있거나, 진실을 아는 자들이 섞인 파티에 함께했던 자들이 파티에 오면 지민이는 그짓말을 칠 수 없습니다.
 
여기서 핵심은 " 진실을 아는 자들이 섞인 파티에 함께했던 자들"또한 제한 범위에 속한다는 부분입니다
이 문제로 인해 단순 반복문이나 배열만으로는 해당 문제를 해결할 수 없게 됩니다. 
이때, Union-Find를 활용하면 해결이 가능합니다. Union-Find는 빠르게 연결망을 하나로 묶어줄 수 있기에 현재 문제에 아주 적합한 알고리즘입니다.

 

최종 코드

#include <iostream>
#include <vector>

using namespace std;

int parent[51];
bool wholeKnow[51];

int find(int x) {
	if (x == parent[x]) return x; //자기자신이 루트
	//다른 숫자가 루트에 존재할때는 최종 루트(자기자신을 루트로 가지는)를 찾을때까지 재귀
	return parent[x] = find(parent[x]);  

}

void unionSet(int a, int b) {
	a = find(a); 
	b = find(b);
	//루트가 다르다면 b의 루트를 a의 루트로 결합
	if (a != b) parent[b] = a; 
}

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

	//기본 수 입력
	int people, party, known, result = 0;
	cin >> people >> party >> known;

	//루트 설정(처음은 자기자신)
	for (int i = 1; i <= people; i++) parent[i] = i;
	
	//진실을 아는 자들
	vector<int> knowns(known);
	for (int i = 0;i < known;i++) {
		cin >> knowns[i];
		wholeKnow[knowns[i]] = true;
	}

	//파티 인원 입력
	vector<vector<int>> partyList(party);
		for (int i = 0;i < party;i++) {
			int n;
			cin >> n;
			partyList[i].resize(n);
			for (int j = 0;j < n;j++) 
				cin >> partyList[i][j];
			//같은 파티끼리 합치기
			for (int j = 1;j < n;j++) //0번째를 기준으로 결합
				unionSet(partyList[i][0], partyList[i][j]);
		}

		//진실을 아는 자들과 같은 집합의 사람들을 knows그룹에 포함
		for (int i = 0;i < known;i++) {
			int root = find(knowns[i]);
			for (int j = 1;j <= people;j++) {
				if (find(j) == root)
					wholeKnow[j] = true;
			}
		}

		//파티별 가능여부 체크
		for (int i = 0;i < party;i++) {
			bool isLie = true;
			for (int j = 0;j < partyList[i].size();j++) {
				//파티인원에 진실을 아는 자가있으면,,
				if (wholeKnow[partyList[i][j]]) {
					isLie = false;
					break;
				}
			}
			if (isLie) result++;
		}

	cout << result;
	return 0;
}

 

 

---

https://www.acmicpc.net/step/14
위에서의 문제는 사실 대표적인 Union-Find 알고리즘은 아닙니다.
위 링크를 통해 들어가면 Union-Find의 개념부터 응용까지 빠르게 습득하기 좋은 커리큘럼으로 4문제가 제공되어있으니 이해가 어렵다면 직접 풀어보는 것도 좋은 방법일 것 같네용
 
그럼 저는 30000

---

참고한 글

https://velog.io/@jxlhe46/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C-Union-Find