[알고리즘] 유니온파인드 (Union-Find)

코딩테스트

 

주제

유니온 파인드

 

설명

• 유니온-파인드(또는 Disjoint-Set)는 서로소 집합(Disjoint Sets)을 효율적으로 관리하는 자료 구조로, 주로 그래프에서 연결성 문제를 해결하는 데 사용됩니다. 이 기법은 다음 두 가지 핵심 연산을 기반으로 작동합니다:
• Find (루트 찾기): 원소가 속한 집합(트리)의 대표자(루트 노드)를 찾습니다.경로 압축(Path Compression)을 통해 트리의 깊이를 줄여 이후 연산을 더 빠르게 수행할 수 있도록 최적화합니다.
• Union (집합 병합): 두 집합을 하나로 병합합니다.크기(Size Union) 또는 랭크(Rank Union)를 기준으로 병합하여 트리의 깊이를 최소화합니다.
• 각각의 리스트에서 각각의 루트노드를 가지고 있는데 필요에 따라 병합해서 루트노드를 공유해서 관리

 

장점

• 효율성: Union과 Find 연산 모두 평균적으로 **O(α(N))**의 시간 복잡도를 가집니다. 여기서 α(N)은 아커만 함수의 역함수로, 거의 상수에 가깝습니다. 크기 비교와 경로 압축을 통해 성능이 최적화됩니다.
• 적용 가능성: 네트워크 연결성 확인, 최소 스패닝 트리(MST) 알고리즘(예: Kruskal's Algorithm), 그리고 친구 네트워크 문제 등 다양한 문제에 적용됩니다.
• 단순한 구현: 배열만으로 간단히 구현 가능하며, 메모리와 연산 모두 효율적입니다.
• 확장성: 동적으로 데이터가 추가되거나 삭제되는 문제에도 대응 가능합니다.

 

코드

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken()) + 1;
        M = Integer.parseInt(st.nextToken());

        ListA = new int[N];
        for (int i = 0; i < N; i++) {
            ListA[i] = i;
        }

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

            if (isUnionOrUnion == 0) {
                Union(a,b);
                System.out.println(Arrays.toString(ListA));
            } else {
                boolean union = isUnion(a, b);
                if (union) {
                    sb.append("YES");
                } else {
                    sb.append("NO");
                }
                sb.append("\n");
            }
        }
        System.out.println(sb);
    }
    
    static int Find(int x) {
        if (x == ListA[x]) return x;
        return ListA[x] = Find(ListA[x]);
    }
    
    static void Union(int x, int y) {
        x = Find(x);
        y = Find(y);
        
        if (x == y) return;
        if (x < y) {
            ListA[y] = x;
        } else {
            ListA[x] = y;
        }
    }
    
    static boolean isUnion(int x, int y) {
        x = Find(x);
        y = Find(y);
        return (x==y);
    }
}

 

알고리즘 기법을 이용한 문제 풀이 

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