관리 메뉴

막내의 막무가내 프로그래밍 & 일상

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

알고리즘/유니온파인드, 최소신장트리(크루스칼)

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

막무가내막내 2020. 11. 7. 20:05
728x90

www.acmicpc.net/problem/1717

 

1717번: 집합의 표현

첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가

www.acmicpc.net

 

 

 

 

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

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

brenden.tistory.com/34

 

[백준 1717] 집합의 표현

글에 개요 백준 알고리즘 1717번 "집합의 표현" 문제입니다. 앞서 다루었던, 아래 참고할 글 1번에 정리한 내용을 보시면 쉽게 푸실 수 있는 문제입니다. 유니온 파인드 (Union-Find)를 정리한 글 내용

brenden.tistory.com

 

 

 

풀이는 다음과 같습니다.

[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]);
        }
    }
}

 

 

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

728x90
Comments