[알고리즘] 백준 1717 집합의 표현 -유니온파인드(Union-find)- 자바

www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

 

 

 

백준 유니온파인드 단계별풀기의 문제입니다.

처음 푸는 유형이라 밑을 참고해서 공부 후 풀었습니다.

brenden.tistory.com/34

[백준 1717] 집합의 표현

 

 

 

풀이는 다음과 같습니다.

[Java]

import java.util.Scanner;

class Main {
    private static int[] parent;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        parent = new int[n + 1]; // [해당노드] = 최상위부모값
        for (int i = 1; i <= n; i++) { //Disjoint-set 만들어줌(상호배타적집합)
            parent[i] = i;
        }
        for (int i = 0; i < m; i++) {
            int flag = sc.nextInt();
            int a = sc.nextInt();
            int b = sc.nextInt();
            if (flag == 0) {
                union(a, b);
            } else {
                if(isSameParent(a,b)){
                    System.out.println("YES");
                }else {
                    System.out.println("NO");
                }
            }
        }
    }

    private static boolean isSameParent(int x, int y) {
        x = find(x);
        y = find(y);
        return x == y;
    }

    private static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) { //서로 최상위부모값이 다르면 합쳐준다,
            if(x < y) parent[y] = x;
            else parent[x] = y;
        }
    }

    private static int find(int x) { //최상위 부모값을 찾는다
        if (x == parent[x]) {
            return x;
        } else {
            return parent[x] = find(parent[x]);
        }
    }
}

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!