[C++] Union&Find 자료구조 - 친구인가?

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를 활용한다.

1. 처음에는 각 학생들에게 서로다른 집합 번호(각 학생들은 학생번호와 같은 집합 번호)를 부여한다.

   for(int i = 1; i <= n; i++){ //각 학생들에게 집합 번호를 부여한다.
       unf[i] = i;
   }​

2. 입력을 하면서 트리구조(학생들을 연결)를 만들어낸다. 하나의 트리가 하나의 집합이 된다.

   for(int i = 1; i <= m; i++){//트리구조 만들어냄, 집합 묶음
       cin >> a >> b;
       Union(a,b);
   }​

3. 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 연결
   }​

    
4. 입력이 끝나면 이와같이 배열에 할당되어있다. 원래 각 학생은 학생번호와 같은 집합번호를 가지고 있었지만 이제는 5번과 9번을 제외하고 모두 자신의 학생번호와 다른 집합번호를 갖게 된다.

   

5. 이제 3번과 8번이 친구인지(같은 집합에 있는지) 확인하고자 한다.

   cin >> a >> b; // 3 8입력
   a= Find(a);//같은 집합에 속한 학생들은 같은 집합번호(루트학생 번호)를 리턴한다.
   b= Find(b);
   if(a==b) cout<<"YES";
   else cout<<"NO";​

6. 위처럼 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]);//루트 학생의 집합번호를 찾음과 동시에 메모이제이션
   }​​

7. 그러면 아래와 같이 배열의 값이 할당된다. Unf[3]의 값이 5(루트의 집합번호==학생번호)로 바뀌었다

8. 만약 1번 학생과 6번 학생이 친구인지 찾는다면?

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/dashboard