백준 1717번 집합의 표현 [JAVA]

문제

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

 

 

출력

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

 

 

예제

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_BJ_1717_집합의표현 {
    static int N,M;
    static int [] arr;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int [N+1];
        
        for(int i=0;i<arr.length;i++) arr[i]=i;
        
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine()," ");
            int o = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            if(o==0) {
                union(a,b);
            }else {
                if(find(a)==find(b)) sb.append("YES\n");
                else sb.append("NO\n");
            }
        }
        System.out.println(sb.toString());
        
    }
    
    public static int find(int x) {
        if(arr[x]==x) return x;
        return arr[x] = find(arr[x]);
    }
    
    public static void union(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);
        
        if(aRoot != bRoot) arr[aRoot] = bRoot;
        
    }
 
}

 

 

풀이방법

두 원소가 같은 집합에 포함되어 있는지를 확인하는 문제였습니다.

변수 o 가 0일 경우에는 두 집합을 합친다는 의미이므로 union()메소드를 통해 각 각의 루트를 찾아 두 원소가 다른 집합일 경우에는 집합의 루트를 같게 해 "두 원소가 같은 집합에 포함되어있다" 라고 표현해주었습니다.

변수 o가 1일 경우에는 두 원소가 같은 집합에 포함되어 있는지 확인하기 위해 find()메소드를 통해 루트가 같은지 확인하여 만약 같다면 yes를, 다르다면 no를 출력해주었습니다.