[ 자료구조 ] Union-Find 알고리즘 (동치류 문제) / 크루스칼 알고리즘

Union-Find 알고리즘

: 정점으로 구성된 집합을 관리하는 방법으로 집합의 합병과 요소가 어떤 부분집합에 속하는가를 판정하는 두 가지 연산.

find 연산으로 특정 원소들을 집합 안에 있는지 없는지 판별하고, 없다면 두 원소들이 속한 트리들을 합병한다.

Union = 2개의 원소로 이루어진 집합을 합치는 연산. = 합집합

Find = 특정 원소가 속한 집합을 찾아주는 연산.

총 세 가지 방법이 있다.

 

첫번째 방법 : 부모 노드 활용

Find 연산

//자기 자신을 가지는 노드로 초기화.
void initgroup() {
  for(i=0;i<n;i++){
    parent[i] = i;
  }
}
 
//x가 속한 트리의 루트 값 반환.
int find(int x) {
  while( x != parent[x] ) {
    x = parent[x];
  }
 
  return x;
}

 

int parent[n] 배열은 각 정점의 부모에 해당하는 정점의 번호가 들어간다. 예로 parent[9] = 4 👉🏻 9번 노드의 부모 노드가 4라는 뜻.

먼저 자기 자신을 루트 노드로 가지도록 초기화 한다.

find 함수에 찾고자 하는 x를 넣어 반복문을 돌게한다. x != parent[x] 즉, x의 루트 노드가 x일 경우 while문을 멈추고 x값 반환.

x = parent[x]로 계속해서 부모 노드로, 그 노드의 부모 노드로 올라가도록 한다.

ex) x가 A에 있는지 없는지 if문으로 확인하기.

if( find(x) == A)
//같으면 같은 집합, 다르면 다른 집합

 

 

Union 연산

//두 개의 정점 a와 b가 속하는 트리의 합집합
void union (int a, int b) {
  parent[find(b)] = find(a)
}
 

 

두 개의 정점 a와 b가 속하는 트리를 합치려면 두 정점을 파라미터로 받고, find 함수를 이용해 각 트리의 루트 값을 찾아낸 다음, b가 속한 트리의 루트 값을 a의 루트값으로 바꿔준다. 즉, 합병한 두 트리의 루트 값은 a가 속한 트리의 루트값.

 

두번째 방법 : Bit-vector 활용

Bit-vector : 중복되지 않은 정수의 집합을 비트로 나타내는 방식

ex) A = {1, 2, 3, 5, 10, 13}, 0부터 시작해서 집합 안의 원소가 나올 때 마다 1을 넣어주면 된다. 0부터 15까지 세었을 때 Bit-vector : 0111 0100 0010 0100. 4자리 씩 끊어 이진법을 계산해보면 7424가 나온다. = 0x 7424

B = {2, 4, 6, 8, 10, 12}    Bit-vector : 0010 1010 1010 1000. = 0x 2AA8

C = {1, 3, 6, 10, 13, 14}.  Bit-vector : 0101 0010 0010 0110. = 0x 5226

 

Find 연산

ex) A 집합 안에 1이 들어있는지 확인하려면 if( A & 0x 4000 != 0 )이어야 한다. 0x 4000은 0100 0000 0000 0000이므로 A와 AND 연산을 했을 때 0이 나오면 1이 들어있지 않은 것이고, 아래와 같이 0이 아니라면 1이 들어있음을 확인할 수 있다.

    0111 0100 0010 0100
AND 0100 0000 0000 0000
_______________________
    0100 0000 0000 0000

 

Union 연산

ex) 집합 A와 집합 B를 합치게 되면 단순히 OR 연산을 해주면 된다. AUB = {1, 2, 3, 4, 5, 6, 8, 10, 12, 13}

    0111 0100 0010 0100
OR  0010 1010 1010 1000
_______________________
    0111 1110 1010 1100

 

세번째 방법 : 연결리스트 활용

ex) A = {1, 2, 3, 5, 10, 13} 👉🏻 (A) -> 1 -> 2 -> 3 -> 5 -> 10 -> 13

 

Find 연산

연결리스트의 검색 연산으로 찾으려는 수 x가 A안에 있는지 없는지 조회한다.

 

Union 연산

A와 B를 합친다면 A의 뒤에 B를 연결한 후, 중복된 원소를 조회해 지워주면 된다.

 

크루스칼 알고리즘을 첫번째 방법 ( : 부모 노드 활용)으로 풀어보기

아래 예시로 쓰인 그래프는 전 글에서 사용한 무방향 가중치 그래프이다. 참고 👇🏻

https://tildacoderecorder.tistory.com/108

[ 자료 구조 ] 신장 트리 / 최소 비용 신장 트리

각 원소마다 자기 자신을 가지고 있도록 초기화한다.

가장 가중치가 낮은 간선 (E, G)를 보면 먼저 Find 연산으로 E와 G가 속한 트리의 루트 값을 찾아본다. find(E) = E, find(G) = G이므로 둘은 서로 다른 집합이다. 이 조건을 만족했으므로 다음으로 넘어가 둘을 합병한다.

위의 union 함수에 E와 G를 파라미터로 넣으면 G의 부모 노드가 E가 된다.

다음 간선인 (A, B)를 보자. find(A) = A, find(B) = B이므로 조건을 만족하기에 union(A, B)로 B의 부모 노드는 A가 된다.

이와 같은 과정을 반복하며 (B, D)의 차례가 되었을 때 다소 헷갈릴 수 있는 부분이 있어 짚고 넘어간다. 이는 (E, F) 간선을 따져볼 때도 똑같이 조심해야한다.

find(B) = A, find(D) = D로 둘은 서로 다른 집합에 속해 있으므로 조건을 만족시킨다. union 함수를 사용하면 union(B, D)로 B의 루트 노드가 D가 속해있는 트리의 루트 노드가 되는데 이는 그림으로 보면 다음과 같다.

B의 루트 노드가 A이므로 D는 루트 노드 A의 밑으로 들어가게 된다. 그렇기에 D의 부모 노드는 A.

이와 같은 이유 때문에 그 다음 간선인 (A, D)를 따져볼 때 A와 D가 같은 트리 안에 있는 원소기 때문에 간선을 삽입하지 못 하게 된다. (사이클이 만들어짐)

위 과정을 반복해 최소 비용 신장 트리를 완성하면 다음과 같다.

 

 

참고 : C로 배우는 쉬운 자료구조 / 이지영 / 한빛아카데미