[백준 java] 1717 - 집합의 표현 (Union-find)

집합의 수는 0을 포함한 N+1 개의 집합을 가진다. 

Union-find 알고리즘을 사용하여 문제를 해결했다.

합집합 찾기라는 의미를 가진 알고리즘으로, 두 개의 노드를 집어 두 노드가 같은 그래프에 속하는지 판별한다.

 

• Find 는 입력한 수가 어떤 집합에 포함되어있는지 부모를 찾아준다
  (재귀함수를 사용하여 부모를 찾을때까지 타고 올라간다)
• Union 은 두 수 a와 b가 포함되어 있는 집합을 합쳐준다.
  두 값을 비교하여 더 작은 값의 부모노드로 합쳐준다
  부모가 p[1] = 1 과 p[2] = 2인 노드를 합치면
  p[2] = 1로 연결되며 더 작은 1번노드를 가리키게 된다

for문으로 M개의 입력(m,a,b)을 받으며

첫번째 숫자의 m이 0이면 a,b를 union

첫번째 숫자m이 1이면 a,b를 각각 find하여 같은 집합에 포함되어있는지 확인한다.

 

 

 

import java.util.Scanner;

public class B1717 {
    static int N,M;
    static int[] parent = new int[1000001];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        // 0~n+1의 수
        for(int i=0; i<=N; i++){
            parent[i] = i;
        }
        for(int i=0; i<M; i++){
            int m,a,b;
            m = sc.nextInt();
            a = sc.nextInt();
            b = sc.nextInt();
            if(m==1) isSameParent(a,b);
            if(m==0) union(a,b);
        }
    }

    private static void isSameParent(int a, int b) {
        a = find(a);
        b = find(b);
        if(a == b)
            System.out.println("YES");
        else
            System.out.println("NO");
    }

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

    private static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if(a != b){
        
        	//값을 비교하여 더 작은 값의 부모노드로 합쳐준다
            // 부모가 p[1] = 1 과 p[2] = 2인 노드를 합치면
            // p[2] = 1로 연결되며 더 작은 1번노드를 가리키게 된다
            if(a < b) parent[b] = a;
            else parent[a] = b;
        }
    }
}