[백준]1717: 집합의 표현 - JAVA

[백준]1717: 집합의 표현

www.acmicpc.net/problem/1717

1717번: 집합의 표현

풀이

문제도 간결하고 읽어보면 알 수 있듯이 union-find문제이다. union-find는 MST의 Kruskal알고리즘에서도 사용되는 이론이므로 꼭 알고있자.

 

풀이도 간단하다. 0을 입력받으면 union, 1을 입력받으면 각 요소의 부모가 같은지 확인후 yes, no를 출력해주면 된다.

 

union함수는 각 요소들의 부모를 같게 만들어 합집합으로 만들어 주는 함수이고, find는 각 요소의 부모를 찾아 반환해주는 함수이다.

 

코드

import java.util.*;
 
public class Main {
    
    static int[] parent;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        parent = new int[n + 1];
        for(int i = 0; i <= n; i++) {
            parent[i] = i;
        }
        
        int m = scan.nextInt();
        for(int i = 0; i < m; i++) {
            int kind = scan.nextInt();
            int num1 = scan.nextInt();
            int num2 = scan.nextInt();
            
            int p1 = find(num1);
            int p2 = find(num2);        
            
            if(kind == 0 && p1 != p2) union(p1, p2);
            else if(kind == 1 && p1 != p2) System.out.println("NO");
            else if(kind == 1 && p1 == p2) System.out.println("YES");
        }
    }
    
    public static void union(int a, int b) {
        parent[a] = b;
    }
    
    public static int find(int a) {
        if(parent[a] == a) return a;
        else return parent[a] = find(parent[a]);
    }
}