[BOJ-1717][Disjoint-Set] 집합의 표현 - Java

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

1717번: 집합의 표현

Disjoint-Set 을 사용하는 가장 기본적인 문제라고 생각합니다.

p[] 배열을 만들고, find() 연산과 union() 연산을 이용하면 쉽게 풀 수 있습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[] p;

    static int find(int a) {
        if(a == p[a]) return a;
        return p[a] = find(p[a]);
    }

    static void union(int a, int b){
        int aRoot = find(a);
        int bRoot = find(b);
        if(aRoot != bRoot) p[bRoot] = aRoot;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken());
        p = new int[n+1];

        for(int i = 1; i<= n; i++) p[i] = i;        //make-set

        for(int i = 0 ; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int menu = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            switch(menu) {
            case 0:
                union(a, b);
                break;
            case 1:
                sb.append(find(a) == find(b) ? "YES\n" : "NO\n");
                break;
            }
        }
        System.out.println(sb.toString());
    }
}

 

먼저 find() 연산입니다.

static int find(int a) {
    if(a == p[a]) return a;
    return p[a] = find(p[a]);
}

파라미터로 들어온 a의 부모를 찾는 메소드입니다. 이때, 루트에 도착하기 전까지 체크하는 친구들의 부모를 모두 루트로 업데이트해줌으로써 뎁스가 무식하게 길어지는 것을 방지해줍니다.

 

 

그 다음은 union() 연산입니다.

static void union(int a, int b){
    int aRoot = find(a);
    int bRoot = find(b);
    if(aRoot != bRoot) p[bRoot] = aRoot;
}

a와 b를 합치는 메소드입니다. 각각의 루트를 구하고 이 둘이 다르면 한 쪽을 다른 한 쪽에 붙여줍니다.

 

 

 

 

간단합니다. 감사합니당.