유니온 파인드 / 분리 집합 / 서로소 집합

백준 1717 골드5(자바)

유니온 파인드

: union 연산 + find 연산 + 대표 노드 개념

• union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산
• find 연산 : 노드가 속한 집합의 대표 노드를 반환하는 연산

유니온 파인드 로직

• 1차원 배열을 이용한다. 인덱스가 노드 번호, 인덱스에 들어있는 값이 그 노드가 속한 집합의 대표 노드 번호.
• 처음에는 노드들이 집합으로 연결되어 있지않기 때문에 각 노드를 대표 노드로 초기화
• find 연산의 경우 대표 노드를 찾는 연산.
  • 찾는 노드(인덱스)에 들어있는 대표 노드로 감
  • 대표 노드 인덱스에 들어있는 대표 노드의 대표 노드로 감
  • 반복하다가 인덱스와 인덱스에 들어있는 대표 노드가 같으면 그 값을 리턴
• union 연산의 경우 2개의 노드(a, b)를 대표 노드로 연결함.
  • b 노드의 대표 노드를 바꾼다고 할 때 b 노드(인덱스)에 들어있는 값을 바로 a 노드에 들어 있는 값으로 바꾸면 안됨
  • a 노드의 대표 노드를 find 연산으로 찾고 b 노드의 대표 노드도 find 연산으로 찾은 뒤 b가 아닌 b의 대표 노드의 값을 a 노드의 대표 노드 값으로 바꿔야 함.
• find 과정에서 반드시 경로 압축이 필요함. 경로 압축이란 find 연산에서 index 5의 값이 4, index 4의 값이 3일 때, find를 하면서 index 5의 값도 3으로 바꿔주는 것을 말함. 경로 압축을 통해 시간 단축이 가능.

백준 1717

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int[] arr;
    public static int N,M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N+1];

        for(int i=0;i<arr.length;i++) {
            arr[i] = i;
        }

        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine());
            int UorF = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if(UorF==0) { //union
                union(a,b);
            }else{
                a = find(a);
                b = find(b);
                if(a!=b){
                    System.out.println("NO");
                }else{
                    System.out.println("YES");
                }
            }

        }

    }

    //대표노드 찾기
    public static int find(int a){
        if(a==arr[a]) return a;
        else{
            //경로 압축
            return arr[a] = find(arr[a]);
        }
    }

    //합치기
    public static void union(int a, int b){
        a = find(a);
        b = find(b);
        if(a!=b){
            arr[b] = a;
        }

    }


}