유니온 파인드

유니온 파인드란 어떤 집합을 나타낼 때 사용한다.

kruskal 알고리즘에서 사이클 생성 여부를 확인할 때 주로 사용된다.

 

상호 배타적 집합(Disjoin-set)이라고도 하는데

2가지 연산으로 이루어져 있다.

1. Find : x가 어떤 집합에 포함되어 있는지 찾는 연산 -> 루트를 찾아내는 연산

2. Union : x와 y가 포함되어 있는 집합을 합치는 연산

 

구현은 간단한 트리를 사용한다.

 

parnet[i]에는 i의 루트가 저장되어 있다.

x와 y를 합치는 경우

parent[x] = x, parent[y] = x 형태로 만들어 준다.

1과 2가 같은 집합이고 4와 5가 같은 집합인 경우엔

 

다음과 같은 형태를 띤다.

 

만약 2와 5를 합친다면 

parnet[i]에는 i의 루트가 저장되어 있기 때문에

parent[5] = 2를 만들면

그림과 같이 아까 합쳤던 4는 동떨어지게 된다.

그렇기 때문에 합치는 연산인 Union연산은

두 집합에 들어있는 모든 것들을 다 합치기 위해

Find연산으로 각각 x, y의 루트를 찾고

합쳐줘야 한다.

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

Find연산은 하나의 파라미터 변수인 x를 받아

x의 루트를 찾아주는 연산으로 재귀 호출로 구현한다.

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

각 집합의 루트는 무조건 parent[i] = i 형태를 띠기 때문에

if(x == parent[x]) 인경우엔 루트를 찾은 경우니까 x를 리턴하고

x와 parent[x]가 다른 경우엔

parent[x]의 값을 매개변수로 find 메소드를 재귀 호출해서

parent[x]값을 초기화하고 그 값을 리턴한다.

 

* 유니온 파인드를 활용한 문제들

   - 백준 1717번 문제 집합의 표현

     https://dundung.tistory.com/104

   - 백준 2606번 문제 바이러스

     https://dundung.tistory.com/105