[Algorithm]집합 - 2. 구현

이전 글

집합(Algorithm) - 1. 개념

 

 

Initialize(초기화)

• 집합에 값을 넣기 앞서 배열을 초기화 한다.
• 2, 3, 4, 6, 7, 8, 9, 11 원소를 초기화 한다고 하면 0~11까지 원소를 담을 수 있는 길이 12의 배열로 초기화 한다.
• 사용하지 않는 원소는 부모 노드(부모 = 배열의 값)가 -1 되게 한다.
• 부모 노드가 자기 자신의 인덱스가 되도록 초기화 해준다. (모든 원소는 대표원소)
• 여기까지 하면 원소가 하나인 집합 8개가 만들어 진다.

int[] elements = {2, 3, 4, 6, 7, 8, 9, 11}; // 초기화 될 집합 원소.
int[] setArray = new int[12]; // 집합 배열

Arrays.fill(setArray, -1); // setArray의 기본 값을 -1로 셋팅

// 원소의 값에 부모 노드가 자기 자신이 되게 초기화 한다.
for(int e : elements) {
    setArray[e] = e; // "setArray[원소의 값] = 부모 노드"
}

< 초기화 된 배열 >

 

집합 A와 집합 B 만들기

< 집합 A와 집합 B >

• 집합 A는 2가 대표 원소이고 6과 9를 포함하고 있다.(집합 A = {6, 9})

//집합A 만들기
setArray[6] = 2;
setArray[9] = 2;

• 집합 B는 3이 대표 원소이고 3은 4, 5을 7은 8, 8은 11을 포함하고 있다.(집합 B = {3, 4, 7, 8, 11})

// 집합B 만들기
setArray[4] = 3;
setArray[7] = 3;
setArray[8] = 7;
setArray[11] = 8;

 

파인드

• 파인드는 어떤 특정 노드의 부모 노드가 무었인지 찾는 방법이다.
• 파인드 연산은 해당 노드가 같은 집합에 속해있는지 확인하기 위해 사용 한다.
• 어떤 노드 x와 y의 루트 노드(대표 원소)가 같으면 같은 집합에 속한 것이다. 예를 들면 위의 그림 집합B에서 {4}와 {8}은 대표 원소가 같다. 따라서 {4}와 {8}은 같은 집합에 해당 된다. ({9}와 {8}은 setArray라는 같은 배열에 있지만 대표노드가 다름으로 같은 집합이 아니다.)
• 위의 그림에 집합B를 보면 {8}의 부모는 {7}이다. 파인드 연산을 한번만 하면 해당 노드의 직계 부모를 알 수 있고 재귀를 통해 루트까지 거슬러 올라간다면 대표 원소인 {3}을 찾을 수 있다.

public static int find(int[] set, int node) {
    return set[node];
}

• 위 코드는 특정 노드의 직계 부모를 찾는 함수 이고 여기서 재귀로직만 추가 하면 대표 원소를 찾을 수 있다.

public static int find(int[] set, int node) {
    // 대표 원소(루트 노드)는 부모가 자기 자신이다.
    // 따라서 배열 set의 인덱스와 배열 set의 값이 같을 때 까지 재귀를 반복 한다.
    if(set[node] == node) {
        return node;
    }
    return find(set, set[node]);
}

• find 연산은 트리의 균형이 잡혀있는 경우라면 O(logn)의 시간 복잡도를 갖지만 편향 트리( / 형태 및 \ 형태)인 경우 O(n)의 시간 복잡도를 가진다. 따라서 가능 하다면 깊이를 최대한 줄이는 것이 성능면에서 좋다. 예를 들면 집합 B의 {11}은 대표 원소를 찾기 위해서 3번의 find() 함수가 호출 되어야 한다. 그런데 {11}을 {8}에서 떼서 대표 원소인 {3}의 자식으로 붙여 준다면 find() 연산 한번으로 어떤 집합에 {11}이 속해 있는지 알 수 있게 된다.

< 트리의 깊이 줄이기 >

setArray[11] = 3;

• {8}도 {3}에 붙여 준다면 집합B는 모든 원소가 단 한번의 find() 연산으로 어떤 집합에 속해 있는지 알 수 있다.

유니온

• 유니온 연산은 두 집합을 하나의 집합으로 합치는 연산이다.
• 두 집합을 합친다는 의미는 두 집합의 루트 노드를 같게 해주는 것이다.
• {집합 A}와 {집합 B}를 예를 들면 B의 대표 원소 {3}을 A의 대표 원소 {2}의 자식으로 옮기거나, 반대로 A의 {2}를 B의 {3} 자식으로 옮기는 방법이 있다.
  1. {9}가 속해있는 집합과 {8}이 속해있는 집합을 서로 합치려 한다.
  2. {9}를 find 연산해 {9}의 루트 노드를 찾는다. {9}의 루트 노드는 {2} 이다.
  3. {8)을 find 연산해 {8}의 루트 노드를 찾는다. {8}의 루트 노드는 {3} 이다.
  4. {8}의 루트 노드인 {3}을 {2}의 자식 노드로 붙여 준다.
  5. 이제 {8}의 루트 노드가 {2}가 되었으므로 두 집합은 합쳐 졌다.

< 집합 A + 집합 B >

• 두 집합은 잘 합쳐 졌지만 트리의 깊이가 깊어진 것을 알 수 있다. 트리의 깊이가 깊어지면 find()의 성능 저하된다고 앞서 말했다. 유니온에서 이 문제를 해결하기 위해서는 트리의 깊이가 더 깊은 집합에 트리의 깊이가 짧은 집합을 합쳐주면 된다. 즉, 깊이가 2인 집합B에 깊이가 1인 집합A을 붙이면 트리의 깊이는 계속해서 2이므로 두 집합이 합쳐지더라도 성능이 저하되지 않는다.  이러한 기법을 랭크라고 한다.
• 아래는 랭크를 적용한 전체 소스

import java.util.Arrays;

public class SetExgample {

    public static void main(String[] args) {
        int[] elements = {2, 3, 4, 6, 7, 8, 9, 11};
        new SetExgample().solution(12, elements);
    }

    int[] elements; // 초기화 될 집합 원소.
    int[] setArray; // 집합 배열
    int[] rankArray; // 트리의 깊이를 저장 할 배열

    public void solution(int n, int[] elements) {
        this.elements = elements;
        this.setArray = new int[n];
        this.rankArray = new int[n];

        Arrays.fill(this.setArray, -1); // setArray의 기본 값을 -1로 셋팅
        Arrays.fill(this.rankArray, -1); // rankArray 기본 값을 -1로 셋팅

        // 원소의 값에 부모 노드가 자기 자신이 되게 초기화 한다.
        for(int e : elements) {
            this.setArray[e] = e; // "setArray[원소의 값] = 부모 노드"
            this.rankArray[e] = 0;
        }

        //집합A 만들기
        addSet(6, 2);
        addSet(9, 2);

        // 집합B 만들기
        addSet(4, 3);
        addSet(7, 3);
        addSet(8, 7);
        addSet(11, 3);

        union(9, 8);
    }

    public void addSet(int add, int parent) {
        this.setArray[add] = parent;
        // 루트 노드의 깊이만 알면 됨으로 sub 노드의 랭크는 -1로 변경
        this.rankArray[add] = -1;
        find(add, 0); // Rank를 계산하기 위한 find() 호출
    }

    public int find(int node, int depth) {
        // 대표 원소(루트 노드)는 부모가 자기 자신이다.
        // 따라서 배열 set의 인덱스와 배열 set의 값이 같을 때 까지 재귀를 반복 한다.
        if(this.setArray[node] == node) {
            // 저장된 깊이 보다 깊이가 깊으면
            if(this.rankArray[node] < depth) {
                // rank 업데이트
                this.rankArray[node] = depth;
            }
            return node;
        }
        return find(this.setArray[node], depth + 1);
    }

    public void union(int nodeX, int nodeY) {
        int rootX = find(nodeX, 0); // nodeX의 루트 노드를 찾는다.
        int rootY = find(nodeY, 0); // nodeY의 루트 노드를 찾는다.

        if(this.rankArray[rootY] > this.rankArray[rootX]) { 
        	// 트리Y가 더 깊을 때
            // nodeX의 루트 노드의 부모를 nodeY의 루트 노드로 바꿔 준다.
            this.setArray[rootX] = rootY;
            // 루트 노드의 깊이만 알면 됨으로 sub 노드의 랭크는 -1로 변경
            this.rankArray[rootX] = -1;
        } else if(this.rankArray[rootY] < this.rankArray[rootX]) {
	        // 트리X가 더 깊을 때
            // nodeY의 루트 노드의 부모를 nodeX의 루트 노드로 바꿔 준다.
            this.setArray[rootY] = rootX;
            // 루트 노드의 깊이만 알면 됨으로 sub 노드의 랭크는 -1로 변경
            this.rankArray[rootY] = -1;
        } else { 
	        // 깊이가 같을 때
            this.setArray[rootY] = rootX;
            this.rankArray[rootY] = -1;
            // 깊이가 같을 때는 최대 깊이가 1이 더 늘어 남.
            this.rankArray[rootX] = this.rankArray[rootX] + 1;
        }
    }

}