[알고리즘] Union Find 알아보기

Union Find

유니온 파인드란 그래프의 관점에서 두 노드가 같은 그래프에 속하는지 빠르게 판별하는 알고리즘이다.
집합에서의 관점으로는 두 요소가 같은 집합에 속하는지 판별한다.
union find 알고리즘은 두 노드가 속하는 집합을 합치는 union 과 두 노드가 같은 집합인지 확인하는 find 연산이 있다.

 

설명

6개의 노드로 union find 의 예시를 들어보겠다.
부모를 알 수 있는 배열을 만드는데, 각 노드는 아직 아무 연결도 되어있지 않으므로 아직 자기자신이 부모이다.

 

 

 

1,2를 한 집합으로 4,5,6을 한 집합으로 묶고자 한다.

 

 

 

 

잘못된 예시

먼저 위의 예시는 잘못된 예시이다.

만약, 이런식으로 부모 노드를 연결한다면 문제가 생길 것 이다.

 

 

 

모든 노드를 연결 한다고 가정했을때 위와 같은 방식으로 부모노드를 연결한다면,

직접 연결된 노드를 찾는 것 과 다를 것 이 없기때문에 union find라는 알고리즘을 쓰는 이유가 없을 것 이다.

 

 

이제 옳은 예시를 보이겠다.

이런식으로 자식을 최 상위 부모를 연결 해준다.

 

 

최적화 x

1,2 와 4,5,6 그래프를 합친 경우이다.

각 노드(그래프)를 합치는 연산이 union(x,y) 이고 

이 최상위 부모를 찾고 업데이트 해주는 연산이 find(x,y) 이다.
위 그래프는 parent를 나타내는 그래프이지, 실제 노드의 그래프 모양은 저것과 다르다.
예를 들어 union(2,5) 라 함은 노드2 와 노드5 를 합치는 것 이다.
하지만, parent그래프의 모양은 2와 5가 직접 연결 되지 않고 위와 같이 되는 것 이다.

이제 최적화 방법 까지 이용을 해서 구현을 할 것 이다.

단순 구현

// 초기화
int parent[MAX_SIZE];
for (int i = 0; i < MAX_SIZE; i++)
    parent[i] = i;

int find(int x) {
    if (parent[x] == x) { // 최상위 노드일때
        return x;
    } else {
        // 부모 노드로 올라간다.
        return find(parent[x]);
    }
}

void union1(int x, int y){
    // 각 노드가 속한 그래프의 최상위 노드를 찾는다.
    x = find(x);
    y = find(y);
	// x가 포함된 그래프에 y가 포함된 그래프 연결
     parent[y] = x;
}

find 최적화

union(5,6) -> union(4,5) -> union(3,4) -> union(2,3) -> union(1,2) 순으로 연결 한다면 
위와 같은 그래프가 형성 될 것 이다.

위에서 말했듯이 이런식으로 형성 된다면 union find 알고리즘을 쓸 이유가 없기 때문에

find 연산에서 부모 노드로 올라가는 과정에서 각 노드의 부모를 업데이트 해 줌으로써 최적화가 가능하다

int find(int x) {
    if (parent[x] == x) { 
        return x;
    } else {
    	// 각 노드마다 부모 업데이트
        return parent[x] = find(parent[x]);
    }
}

union 최적화 & 전체 코드

union연산 최적화는 depth가 큰 그래프 밑에 depth가 작은 그래프를 붙이는 조건을 거는 것 으로 최적화가 가능하다.

int parent[MAX_SIZE];
int depth[MAX_SIZE]; // 트리의 깊이
for (int i = 0; i < MAX_SIZE; i++) {
  parent[i] = i;
  depth[i] = 1; 
}

int find(int x) {
    if (parent[x] == x) { 
        return x;
    } else {
        return parent[x] = find(parent[x]);
    }
}

void union1(int x, int y){
   x = find(x);
   y = find(y);

   // x == y 이면 x, y가 같은 그래프 라는 뜻
   if(x == y)
     return;

   //depth가 깊은 그래프 밑에 depth 가 작은 그래프를 넣는다.
   if(depth[x] < depth[y]) {
     parent[x] = y; 
   }
   else {
     parent[y] = x;

     if(depth[x] == depth[y])
       depth[x]++; // 높이가 같으면 합친 후 깊이 + 1
   }
}