[Java] 집합의 표현 - 유니온 파인드 (Lv. Gold5)

집합의 표현 - 유니온 파인드 (Lv. Gold5)

---

1. 문제

2. 풀이

---

1. 문제

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

 

2. 풀이

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

class Main {
    static int[] par;
        
    public static int _find(int A) {
        if (par[A] == A) return A;
        return par[A] = _find(par[A]);
    }
    
    public static void _union(int A, int B) {
        int rootA = _find(A);
        int rootB = _find(B);
        
        if (rootA != rootB) {
            par[rootB] = rootA;
        }
    }
    
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        par = new int[N + 1];
        
        for (int i = 0; i <= N; i++) {
            par[i] = i;
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int X = Integer.parseInt(st.nextToken());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            
            if (X == 0) {
                _union(A, B);
            } else {
                if (_find(A) == _find(B)) {
                    sb.append("YES\n");
                } else {
                    sb.append("NO\n");
                }
            }
        }
  
        System.out.print(sb);
    }
}

 

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

집합을 관리하고 두 원소가 같은 집합에 있는지 판별하는 문제 해결 방식입니다.

 

1. _union 함수에서 A와 B가 속한 집합을 합침

public static void _union(int A, int B) {
    int rootA = _find(A);
    int rootB = _find(B);

    if (rootA != rootB) {
        par[rootB] = rootA;
    }
}

 

A와 B의 부모를 찾고, 부모가 같지 않으면 B의 부모를 A로 설정합니다.

 

2. _find 함수에서 A가 속한 집합을 찾기

public static int _find(int A) {
    if (par[A] == A) return A;
    return par[A] = _find(par[A]);
}

 

처음에 par 배열을 모두 자기 자신을 가리키도록 초기화 했습니다. 만약 A가 자기 자신을 가리키면 자신이 최상위 루트인 것이기 때문에 A를 반환해주고, A가 자기 자신을 가리키지 않으면 최상위 루트를 찾기 위해 find를 해줍니다. 이때 _find(par[A])만 사용하지 않고, par[A] = _find(par[A]); 를 해줌으로써 경로를 압축하여 트리 높이가 줄어들어 시간 복잡도가 낮아집니다.

---

문제가 있으면 댓글 남겨주세요 !

피드백은 언제나 환영입니다 <3