[분리 집합] 분리집합(Disjoint Set)과 유니온-파인드(Union-Find)

분리 집합

분리집합이란 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합, 즉 서로소 집합이다. 따라서 A ∩ B = Ø가 성립된다. 

유니온 파인드

이러한 분리집합은 유니언 파인드 자료구조를 사용한다. 

 

Find 연산

각 트리셋의 자식 노드가 루트(최상위 노드)를 찾는 과정

find(x)

• 찾는 노드에 들어있는 대표 노드로 감
• x와 x의 부모가 같다면 x를 리턴
• 그렇지 않다면 재귀적으로 find를 수행

x의 x의 부모가 같다면 그 노드는 루트 노드이다.

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

 

Union연산

한 트리셋의 루트가 다른 트리셋의 루트를 가르키게 하여 트리를 병합하는 과정

Union(x,y)

 

union은 트리를 병합하는 과정이다.

위에서 만든 find로 각 트리의 대표 노드를 찾고, 같지 않을 경우 B가 아닌 B의 대표 노드의 값을 A 노드의 대표 노드 값으로 바꿔야 한다. 

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

 

 

예시문제: 거짓말:1043번

import java.io.*;
import java.util.*;

public class _1043 {
    static int[] parents;
    static ArrayList<Integer>[] party;
    public static void main(String[] args)throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int n=Integer.parseInt(st.nextToken()); //사람의 수
        int m=Integer.parseInt(st.nextToken()); //파티의 수

        st=new StringTokenizer(br.readLine());
        int t=Integer.parseInt(st.nextToken()); //진실을 아는 사람의 수
        int[] tIdx; //진실을 아는 사람
        party=new ArrayList[m];
        parents=new int[n+1];

        if(t>0) {
             tIdx= new int[t];
            for (int i = 0; i < t; i++) {
                tIdx[i]=Integer.parseInt(st.nextToken());
            }
        }else{
            System.out.println(m);
            return;
        }
        for(int i=0;i<m;i++){
            st=new StringTokenizer(br.readLine());
            party[i]=new ArrayList<>();
            int size=Integer.parseInt(st.nextToken());
            for(int j=0;j<size;j++){
                party[i].add(Integer.parseInt(st.nextToken()));
            }
        }

        for(int i=0;i<=n;i++){
            parents[i]=i;
        }

        //각각 파티 집합으로 묶어주기
        for(int i=0;i<m;i++){
            int a=party[i].get(0);
            for(int j=1;j<party[i].size();j++){
                union(a,party[i].get(j));
            }
        }

        int cnt=0;
        //같은 집합에 속해있는지 확인
        for(int i=0;i<m;i++){
            int leader=party[i].get(0);
            boolean flag=true;
            for(int j=0;j<t;j++){
                if(isitsame(leader,tIdx[j])){
                    flag=false;
                    break;
                }
            }
            if(flag)
                cnt++;
        }
        System.out.println(cnt);
    }

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

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

    static boolean isitsame(int x, int y){
        if(find(x)==find(y))
            return true;
        else {
            return false;
        }
    }
}