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

[ 유니온 파인드란 ? ]

 

합집합을 찾는 대표적인 알고리즘 

Disjoint-Set이라고도 부른다.

 

- Union : 노드 X가 포함된 집합과 노드 Y가 포함된 집합을 하나로 합친다.

- Find :  노드 X가 포함된 집합을 찾아준다.

 

[ 구현 ]

 

- i는 노드번호, parent[i]는 i 노드의 부모 노드를 저장 

 

 

[그림 1]

[그림 1]과 같이 처음에는 parent[i] 를 자기 자신인  i로 초기화한다.

 

 

 

[그림 2]

Union(1,2) Union(3,4)을 통해 그림 2와 같이 변한다. 

노드 2의 부모 노드는 1이 되고 , 노드 4의 부모 노드는 3이 된다. 

 

 

 

[그림 3]

 

Union(1,3)을 통해 노드 3의 부모 노드는 1이 된다. 

따라서 1,2,3,4가 하나의 집합에 포함되는 것을 확인할 수 있다.

 

 

[ Find 함수 ] 

 

위에서 설명한 것과 같이 parent[i]는 처음에 i로 초기화 한다.

 

	for(int j=0;j<N;j++)
        {
            parent[j] = j;
        }
        

find 함수는 해당 노드의 부모 노드를 return 한다.

 

루트 노드는 자신의 index와 parent[idx]가 같으므로

idx == parent[idx] 를 만족할 때까지 재귀를 통해 find 함수를 호출한다.

 

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

 

 

[ Union  함수 ]

 

idx1과 idx2의 부모 노드를 find 함수를 통해서 찾는다.

이 때 indx1 ,idx2 가 다르다면 부모 노드가 다른 것이므로

idx2의 부모 노드를 idx1으로 update해주어 같은 set에 속하게 된다.

 

int unit(int idx1, int idx2)
{
    idx1 = find(idx1);
    idx2 = find(idx2);
    
    if(idx1 != idx2 ) // 서로 부모가 다르다면
    {
        parent[idx2] = idx1;        
    }
}