[백준] 1717번: 집합의 표현 - java

https://www.acmicpc.net/problem/1717

유니온 파인드(Union-Find) 알고리즘은 합집합 찾기(Disjoint Set Union, DSU)라고도 불리며, 상호 배타적 집합을 관리하는 자료구조입니다. 주로 네트워크 연결, 동적 연결성 문제, 최소 신장 트리 알고리즘(크루스칼 알고리즘) 등에서 사용됩니다. 유니온 파인드 알고리즘은 다음 두 가지 주요 연산을 지원합니다:

1. Find: 주어진 원소가 속한 집합을 찾는 연산. 대표 원소(루트)를 반환합니다.
2. Union: 두 집합을 하나의 집합으로 합치는 연산.

 

1. 문제 해석

 

경로압축 알고리즘인 유니온 파인드를 우선적으로 공부를 한 다음에 학습을 시작했다. 이 알고리즘은 말 그대로 유니온이라는 함수와 파인드 함수 두가지로 이루어진 압축 알고리즘이다.

 

처음 parent 배열에 원소의 인덱스에 순서대로 넣고 초기화를 진행한다. 

for(int i=0; i<n+1; i++){
    parent[i] = i; //초기화
}

 

그 다음 유니온, 파인드 함수를 구현해준다.

private static void union(int a, int b) {
    a = find(a);
    b = find(b); 
    if(a!=b){
        parent[b] = a;
    }
}

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

 

여기서 파인드는 노드값과 인덱스 값이 같지 않다면 같을때까지 들어가서 리턴해준다. 여기서 핵심은 else에 return에서 parent[a]에 값을 저장함으로써 압축알고리즘을 진행한다는 점이다. union은 합집합 연산을 하기 위헤 서로 연결되어있지 않다면 부모 인덱스의 값을 a로 바꿔주는 함수이다.

 

 

전체 코드

 

import java.io.*;
import java.util.*;
public class Main {
    static int parent[];
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        parent = new int[n+1];
        for(int i=0; i<n+1; i++){
            parent[i] = i; //초기화
        }
        
        for(int i=0; i<m; i++){
            int question = sc.nextInt();
            int a = sc.nextInt();
            int b = sc.nextInt();

            if(question == 0){ //union
                union(a,b);
            }else{ //같은지 확인
                boolean result = checkSame(a, b);
                if(result){
                    System.out.println("YES");
                }
                else{
                    System.out.println("NO");
                }
            }

        }
        
    }

    private static void union(int a, int b) {
        a = find(a);
        b = find(b); 
        if(a!=b){
            parent[b] = a;
        }
    }

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

    private static boolean checkSame(int a, int b){
        a = find(a);
        b = find(b);

        if(a == b) return true;
        return false;
    }
}

 

완성