백준 1717 집합의 표현 Java

정답률은 29%이지만 유니온 파인드를 활용한다면 쉽게 해결할 수 있는 문제인 집합의 표현이다.

https://dundung.tistory.com/103 

유니온 파인드

문제의 내용은

0부터 N까지 N+1개의 수가 있고 2가지의 명령이 있다.

0번 명령은 x와 y 각각의 집합을 합치는 연산을 하면되고

1번 명령은 x와 y 두 원소가 같은 집합에 포함되어 있는지를 YES or NO로 출력하면 된다.

 

0번 명령은 유니온 파인드의 union메소드를 호출하면 되고

1번 명령은 유니온 파인드의 find메소드를 통해 x와 y의 루트가 같은지 확인하면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Q1717 {
    public static int [] parent;
    
    public static int find(int x) {
        if(x == parent[x]) 
            return x;
        return parent[x] = find(parent[x]);
    }
    
    public static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if(x!=y) {
            parent[y] = x;
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        parent = new int[n+1];
        for(int i=0; i<=n; i++) {
            parent[i] = i; //parent 초기화
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<m; i++) {
            st = new StringTokenizer(reader.readLine());
            int o = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            if(o==0) {
                union(x,y);
            } else {
                if(find(x)==find(y)) {
                    sb.append("YES\n");
                } else {
                    sb.append("NO\n");
                }
            }
        }
        System.out.print(sb.toString());
    }
}