유니온 파인드 (Union-Find)

유니온 파인드 (Union-Find)

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

 

그림으로 이해하기

노드의 개수만큼 아래와 같이 모든 값이 자기 자신을 가리키도록 한다.

i : 노드번호, P[i] : 부모노드 번호 를 의미하며, 즉 자기자신이 어떤 부모에 포함되어 있는지를 의미한다

간단히 Parent[i] = i 로 표현한다

 

Union(1,2) 를 하면 2번째 인덱스에 "1" 값이 들어간다.

부모를 합칠 때는 일반적으로 더 작은 값 쪽으로 합친다. 이것을 합침 Union 의 과정이라고 할 수 있다.

 

Union(2,3) 을 할 경우에는 재귀함수를 통해 부모를 찾는다.

2의 부모 1가 3은 자기자신이기 때문에 결과적으로 3도 "1"의 값을 갖게되어 아래와 같이 바뀐다.

즉, 2,3은 같은 부모인 "1"을 가지고 있기 때문에 둘은 연결되어 있다고 할 수 있다.

 

알고리즘 코드

package test;

public class UnionTest {

    static int[] parent = new int[100];

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

    public static  void union(int x, int y){
        x = find(x);
        y = find(y);

        // 같은 부모를 가지고 있지 않으면
        if(x != y){

            // y가 x보다 크다는 가정하에 아래와 같이 표현
            parent[y] = x;
        }
    }

    //같은 부모인지 확인
    public static boolean isSameParent(int x, int y) {
        x = find(x);
        y = find(y);

        if(x == y){
            return true;
        }else{
            return false;
        }
    }

    public static void main(String[] args) {
        for(int i=1; i <= 8; i++){
            parent[i] = i;
        }

        union(1,2);
        union(2,3);
        union(5,6);
        union(6,7);

        System.out.println("1과 3은 친구인가요?" + isSameParent(1,3));
        System.out.println("1과 5은 친구인가요?" + isSameParent(1,5));
    }
}