Union & Find는 서로소를 찾아내는 자료구조이다.
#include <iostream>
using namespace std;
int unf[1001];//1차원 배열의 트리형태
int Find(int v){
//v라는 학생의 집합번호를 리턴하는 역할
//결국 연결된 집합의 학생들은 루트번호학생의 번호가 집합번호가 되어 리턴함.
if(v==unf[v]) return v;
else return unf[v] = Find(unf[v]);//재귀적으로 루트의 집합번호를 찾아간다.
}
void Union(int a, int b){
a = Find(a);
b = Find(b);
if(a!=b) unf[a] = b;//서로 다른 집합에 있다. unf[1] = 2 : 1-2 연결
}
int main() {
int n,m,a,b;
cin >> n >> m;
for(int i = 1; i <= n; i++){ //각 학생들에게 집합 번호를 부여한다.
unf[i] = i;
}
for(int i = 1; i <= m; i++){//트리구조 만들어냄, 집합 묶음
cin >> a >> b;
Union(a,b);
}
cin >> a >> b;
a= Find(a);//같은 집합에 속한 학생들은 같은 집합번호(루트학생 번호)를 리턴한다.
b= Find(b);
if(a==b) cout<<"YES";
else cout<<"NO";
return 0;
}
- 두 학생이 친구인지를 알기 위해 연결된 친구들은 집합으로 묶어 서로가 같은 집합에 있는지 아닌지를 판별하기 위해 Union&Find를 활용한다.
- 처음에는 각 학생들에게 서로다른 집합 번호(각 학생들은 학생번호와 같은 집합 번호)를 부여한다.
for(int i = 1; i <= n; i++){ //각 학생들에게 집합 번호를 부여한다. unf[i] = i; }
- 입력을 하면서 트리구조(학생들을 연결)를 만들어낸다. 하나의 트리가 하나의 집합이 된다.
for(int i = 1; i <= m; i++){//트리구조 만들어냄, 집합 묶음 cin >> a >> b; Union(a,b); }
- Union은 각 학생들의 집합번호를 가져와서 집합번호가 서로 다르면 연결시켜준다.
void Union(int a, int b){ a = Find(a);//a학생의 집합번호 b = Find(b);//b학생의 집합번호 if(a!=b) unf[a] = b;//서로 다른 집합에 있다. unf[1] = 2 : 1-2 연결 }
- 입력이 끝나면 이와같이 배열에 할당되어있다. 원래 각 학생은 학생번호와 같은 집합번호를 가지고 있었지만 이제는 5번과 9번을 제외하고 모두 자신의 학생번호와 다른 집합번호를 갖게 된다.
- 이제 3번과 8번이 친구인지(같은 집합에 있는지) 확인하고자 한다.
cin >> a >> b; // 3 8입력 a= Find(a);//같은 집합에 속한 학생들은 같은 집합번호(루트학생 번호)를 리턴한다. b= Find(b); if(a==b) cout<<"YES"; else cout<<"NO";
- 위처럼 Find를 호출하게 되는데 Find를 살펴보면 학생 번호와 집합 번호가 같으면 그대로 출력을 하지만 그렇지 않다면 누군가와 연결되어 있다는 뜻이다.(Union함수에서 unf[a]=b로 연결시켜줌). 따라서 연결된 마지막까지 찾아가기 위해 재귀적으로 Find를 호출한다. 결국 학생 자기자신의 번호와 집합번호가 일치한 구간(5,9)에서 각자 자신의 집합번호를 리턴시켜줄 것이다.
int Find(int v){ //v라는 학생의 집합번호를 리턴하는 역할 if(v==unf[v]) return v; else return unf[v] = Find(unf[v]);//루트 학생의 집합번호를 찾음과 동시에 메모이제이션 }
- 그러면 아래와 같이 배열의 값이 할당된다. Unf[3]의 값이 5(루트의 집합번호==학생번호)로 바뀌었다
8. 만약 1번 학생과 6번 학생이 친구인지 찾는다면?
https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/dashboard
'기타등등 > 알고리즘 기록' 카테고리의 다른 글
[C++] Prim MST 알고리즘(Greedy, priority queue활용) - 원더랜드 (0) | 2021.08.06 |
---|---|
[C++] Kruskal MST 알고리즘(Greedy, Union & Find 활용) - 원더랜드 (0) | 2021.08.06 |
[C++] 이항계수(메모이제이션) (0) | 2021.08.06 |
[C++] priority_queue(힙 응용) - 최대 수입 스케쥴 (0) | 2021.08.06 |
[C++] BFS - 송아지 찾기 (0) | 2021.08.05 |