11. 유니온 파인드

11.md

0.00MB

0. 복습
1. Union-Find Tree (Disjoint Set)

Union과 Find 연산이 있는 tree를 저렇게 부른다.

(1) (2) (3) (4) (5) 이렇게 다섯 그룹이 있을 때

1, 2를 union 하면 => (1, 2) (3) (4) (5)

또 3, 4를 union 하면 => (1, 2) (3, 4) (5)

여기서 find(3)을 하면 3이 속한 그룹의 대표자를 찾을 수 있다.

find(4)를 하면 find(3)과 같은 값이 나온다.

이 자료구조의 단점은 c++에 구현이 안되어있다는 것과

find, union 연산의 시간복잡도는 평균 아커만함수의 역함수를 가진다. O(1)이라고 보면 된다.

첫번째 구현방법 :

#include <iostream>
using namespace std;

const int MN = 10;
int par[MN];

void init(int N) { // 트리를 N개 만들었다.
    for(int i=0; i<N; ++i){
        par[i]=i;
    }
}

int find(int x) { // 해당 트리의 루트를 찾는다.
    if(par[x]==x)
        return x;
    else
        return find(par[x]);
}

void unite(int x, int y){ // union이 예약어여서 대체
    x=find(x); y=find(y); // 대표자 찾기
    par[x]=y; // 대표자 바꿔치기
}

int main(){
    init(MN);
    while(true) {
        cout << "합칠 원소 입력 : " << '\n';
        int A, B; cin >> A >> B;
        unite(A-1, B-1);
        for(int i=0; i<MN; ++i){
            printf("%4d", i+1);
        }
        cout << '\n';
        for(int i=0; i<MN; ++i){
            printf("%4d", find(i)+1);
        }
        cout << '\n';
    }
}

하지만 이 구현방법은 O(N)이 걸린다.

최적화를 해야한다. : 경로 압축

find연산 이후 트리를 펼친다고 생각하면 된다.

find()연산에서 살짝만 수정해주면 된다.

int find(int x) { // 해당 트리의 루트를 찾는다.
    if(par[x]==x)
        return x;
    else
        return par[x] = find(par[x]);
}

문제만 풀꺼면 여기까지 알아도 된다.

하지만 최적화 할 수 있는 것이 하나 더 있다.

트리의 깊이가 얕은 쪽을 깊은쪽 밑에 합쳐주는 것.

#include <iostream>
using namespace std;

const int MN = 10;
int par[MN]; // 해당 원소의 부모.(혹은 대표자)
int rnk[MN]; // rank, 트리의 깊이의 상한, 최악의 경우를 방지하기 위해 사용

void init(int N) { // 트리를 N개 만들었다.
    for(int i=0; i<N; ++i){
        par[i]=i, rnk[i]=1;
    }
}

int find(int x) { // 해당 트리의 루트를 찾는다.
    if(par[x]==x)
        return x;
    else
        return par[x] = find(par[x]);
}

void unite(int x, int y){ // union이 예약어여서 대체
    x=find(x); y=find(y); // 대표자 찾기
    if(x==y) return;
    if(rnk[x]>rnk[y]) { // 트리의 깊이가 얕은 쪽이 깊은쪽 밑에 합쳐지도록.
        swap(x, y);
    }
    par[x] = y; // x의 부모를 y로 변경.
    if(rnk[x] == rnk[y]){
        rnk[y]++; // x의 부모가 y로 변경되었으니 y의 rnk만 ++.
    }
}

int main(){
    init(MN);
    while(true) {
        cout << "합칠 원소 입력 : " << '\n';
        int A, B; cin >> A >> B;
        unite(A-1, B-1);
        for(int i=0; i<MN; ++i){
            printf("%4d", i+1);
        }
        cout << '\n';
        for(int i=0; i<MN; ++i){
            printf("%4d", find(i)+1);
        }
        cout << '\n';
    }
}

참고 문제 : 1717, 1976, 4195

2. 최소 스패닝 트리

스패닝 트리 : 그래프에서 몇개의 간선을 지워서 트리로 만든 트리.

최소 스패닝 트리 : 스패닝 트리에서 간선의 합이 최소일 때.

알고리즘은 크루스칼, 프림이 대표적이며, 이번 시간엔 크루스칼 알고리즘을 주로 다룬다.

준비물 : union-find

(1) 간선들을 가중치 기준으로 정렬한다.(오름차순)

(2) 정렬한 가중치들을 겹치지 않게(같은 그룹에 속하지 않게) 선택한다.

참고 문제 : 1197, 2887, 1647