유니온 파인드(Union - Find)

목차

 

 

개요

 

• 대표적인 그래프 알고리즘으로 '합집합 찾기'라는 의미를 가지고 있습니다.
• 상호 배타적 집합(Disjoint - set)이라고도 합니다.
• 여러 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 입니다.
• 2가지 연산으로 이루어져 있습니다.
  • Find : x가 어떤 집합에 포함되어 있는지 찾는 연산
  • Union : x와 y가 포함되어 있는 집합을 합치는 연산

 

구현

 

부모노드를 저장할 배열 생성

int[] parent = new int[10];

for(int i = 0; i < 10; i++)
{
	parent[i] = i;
}

구현은 간단한 트리를 통해서 이루어집니다.

parent[i] 를 i 노드의 부모 노드 라고 정의하고 초기화합니다.

parent[i] = i 인 경우, 루트노드 임을 의미합니다.

 

 

 

find 함수 구현

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

x == parent[x] 라면 부모노드가 자기자신, 즉 본인의 루트노드라는 의미입니다. 부모노드를 찾으면 바로 return을 해줍니다. 그렇지 않은 경우 재귀적으로 루트를 찾아 반환해줍니다.

하지만 위와 같이 find를 구현하면 문제가 하나 발생합니다. 

 

 

위 그림과 같이 한 쪽으로만 tree 가 치우쳐진 경우, find 함수가 루트노드를 찾는데 O(N) 의 시간복잡도가 걸려 tree 로 구현하는 이점이 사라집니다. 이를 개선하기 위해 다음과 같이 구현할 수 있습니다.

 

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

 

 

루트노드인 y를 찾았으면 x의 부모를 바로 루트노드로 바꿔줍니다. 결과적으로 아래 그림과 같이 바뀌어서 find의 효율을 늘릴 수 있습니다.

 

 

union 함수 구현

void union(int x, int y)
{
    x = find(x);
    y = find(y);
    
    if(x != y)
    {
    	if(x < y) parent[y] = x;
        else parent[x] = y;
    }
}

union 함수는 매개변수로 두 개의 값을 받습니다. 두 노드가 각각 포함되어 있는 집합을 합쳐주는 작업을 합니다. 편의상 작은 값으로 합칩니다.

 

 

 

 

 

 

참조

https://ssungkang.tistory.com/198

[Algorithm] 유니온 파인드(Union - Find)

https://brenden.tistory.com/33

[알고리즘] 유니온 파인드 (Union-Find)