알고리즘/알고리즘 스킬

[C++] unionFind

이영재의오른발 2022. 12. 28. 00:09
반응형

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#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의 부모는 다릅니다.";
    }
    
}
 
 
cs

 

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


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

728x90
반응형