[자료구조] Union Find

doiiollo·2020년 6월 7일
1

자료구조

목록 보기
1/1
post-thumbnail

정의

Union-Find 자료구조는 상호 배타적 집합, 서로소 집합 (Disjoint Set)을 표현하기 위한 자료구조이다.




연산

Union-Find 자료구조를 구성하는 연산은 기본적으로 3가지가 존재한다.

  1. init : 모든 원소가 서로 다른 집합에 속하게 한다.
  2. union : 두 원소를 하나의 집합으로 묶어준다.
  3. find : 특정 원소가 어떤 집합에 속하는지 알려준다.



구현

구현 1 : 배열을 이용한 방법

group[i] : i번 원소가 속하는 집합의 번호를 나타낸다.

1. init

static void init(int n) {
    for(int i = 1; i<=n; i++) {
        group[i] = i;
    }
}

2. find - O(1)

특정 원소가 어떤 집합에 속하는지 알아내는 연산을 수행한다.

static int find(int v) {
    return group[v];
}

3. union - O(N)

두 원소가 주어지면 각각의 원소가 속한 집합의 모든 원소들을 같은 집합의 번호로 바꾸어준다.

static boolean union(int u, int v) {
    u = find(u); v = find(v);
    
    if(u == v) return true;
    for(int i = 1; i<=n; i++) {
        if(group[i] == v) group[v] = u;
    }
    return false;
}



구현 2 : 트리를 이용한 방법

group[i] : i번 노드의 부모 노드를 나타낸다.

1. init

static void init(int n) {
    for(int i = 1; i<=n; i++) {
        group[i] = i;
    }
}

2. find - Best : O(1), Worst : O(N)

특정 노드가 속한 집합은 그 노드가 속한 트리의 루트 노드 번호로 나타낼 수 있다.

find 연산에서 특정 노드에서 시작하여 부모 노드로 하나씩 올라가다보면 마지막에 루트 노드에 다다를 수 있고 해당 루트 노드의 번호가 특정 노드가 속한 집합이 된다.

static int find(int v) {
    if(v == group[v]) return v;
    return find(group[v]);
}

3. union - O(N)

두 원소가 다른 트리에 속해 있다면, 트리 하나를 선택하여 다른 트리의 자손으로 넣어 두 트리를 합쳐준다.

static boolean union(int u, int v) {
    u = find(u); v = find(v);
    
    if(u == v) return true;
    group[v] = u;
    return true;
}



구현 3 : 트리를 이용한 구현 최적화

트리를 이용한 Union-Find 구현은 최악의 경우 Skewed Tree 가 만들어 질 수 있으며 이는 unionfind 연산 모두 O(N) 이 되어버린다.

이 문제를 해결하기 위한 방법으로 두 가지 최적화 방법이 있다.




1. Union by Rank

이 최적화 방법은 Union 단계에서 적용할 수 있는 방법으로 두 트리를 합칠 때 높이가 더 낮은 트리를 높이가 높은 트리의 밑에 자손으로 넣어주는 방식으로 최적화를 진행한다.

rank[i] : i번 노드를 루트로 하는 트리의 높이를 나타낸다.
group[i] : i번 노드의 부모 노드를 나타낸다.

static void init(int n) {
    for(int i = 1; i<=n; i++) {
        group[i] = i;
        rank[i] = 1;
    }
}

static int find(int v) {
    if(v == group[v]) return v;
    return find(group[v]);
}

static boolean union(int u, int v) {
    u = find(u); v = find(v);
    
    if(u == v) return true;
    // u를 기준으로 하므로 u의 높이를 항상 더 크게 만들어준다. 
    if(rank[u] < rank[v]) swap(u, v);
    group[v] = u;
    if(rank[u] == rank[v]) rank[u] += 1;
}



2. Path Compression

위의 방법에서 한 가지 최적화를 더 진행해주면 연산의 수행속도를 높힐 수 있다.

find 연산을 수행할 때 거쳐가는 모든 노드를 루트 노드 바로 밑에 붙여주면, 다음 find 연산을 수행할 때 연산량이 줄어들게 되는데 이러한 방법을 Path Compression 이라고 한다.

static void init(int n) {
    for(int i = 1; i<n; i++) {
        group[i] = i;
        rank[i] = 1;
    }
}

static int find(int v) {
    if(v == group[v]) return v;
    // path compression
    return group[v] = find(group[v]);
}

static boolean union(int u, int v) {
    u = find(u); v = find(v);
    
    if(u == v) retun true;
    // union by rank
    if(rank[u] < rank[v]) swap(u, v);
    group[v] = u;
    if(rank[u] == rank[v]) rank[u] += 1;
}



응용

응용 1 : 두 원소를 하나의 집합으로 합치고 원소의 개수 찾기

  • 두 원소가 속한 집합이 같을 경우 : 1 을 반환한다.
  • 두 원소가 속한 집합이 다를 경우 : 두 집합을 하나의 집합으로 만든다 root 가 되는 집합의 원소에 합쳐지는 집합의 원소의 개수를 더하고 child 가 되는 집합의 원소를 1로 초기화한다.
static int union(int u, int v) {
    u = find(u); v = find(v);
    
    if(u == v) return element[v];
    group[v] = u;
    element[u] += element[v];
    element[v] = 1;
    return element[u];
}



응용 2 : Hash Map 을 이용한 구현 방법

find

static int find(int u) {
    if(!map.containKey(u)) {
        map.put(u, u + 1);
        return u + 1;
    } else {
        int v = find(map.get(v));
        map.put(u, v);
        return v;
    }
}
profile
고수가 되고 싶어요

0개의 댓글