[C++] unionFind

 

#include <iostream>
 
using namespace std;
 
int arr[11];
 
// 연결된 부모가 없으므로 자기 자신으로 초기화 
void init() {
    for(int i=0; i<11; i++) {
        arr[i] = i;
    }
}
 
// 부모 찾기 
int find(int x) {
    if(arr[x] == x) { return x; }
    return arr[x] = find(arr[x]);
}
 
// 부모가 같은지 확인 
bool isUnion(int x,int y) {
    x = find(x);
    y = find(y);
    if(x == y) { return true; }
    return false;
}
 
// 부모 만들기 
void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) { return; }
    arr[y] = x;    // y 의 부모는 x 
}
 
int main() {
    init();
    merge(1,3);
    merge(3,5);
    merge(5,7);
    
    if(isUnion(3,7)) {
         cout << "3 과 7의 부모는 같습니다.";
    }
    else {
        cout << "3과 7의 부모는 다릅니다.";
    }
    
}
 
 

 

프로그래머스 섬 연결하기를 풀며 사용된 알고리즘

가끔 나올 수도 있으니 잘 외워두자