[ 백준 / BOJ 1717 ] 집합의 표현 ( 자바 / JAVA )

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

문제

---

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

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

입력

---

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

출력

---

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

풀이

---

parent[] 변수를 두어서 같은 집합에 속해있는지 확인 ‼️

합집합은 unionSet(int a, int b); 함수로 parent[b] 를 parent[a]와 동일하게 만들어준다 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_BOJ_1717_집합의표현 {

    static int n, m;
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());

        n = Integer.parseInt(stringTokenizer.nextToken());
        m = Integer.parseInt(stringTokenizer.nextToken());

        parent = new int[n+1];
        for(int i = 0 ; i <= n ; i++)
            parent[i] = i;

        for(int i = 0 ; i < m; i++){
            stringTokenizer = new StringTokenizer(br.readLine());
            int input = Integer.parseInt(stringTokenizer.nextToken());
            int a = Integer.parseInt(stringTokenizer.nextToken());
            int b = Integer.parseInt(stringTokenizer.nextToken());

            if(input == 0){
                unionSet(a,b);
            }
            else{
                if(find(a) == find(b))
                    sb.append("YES").append("\n");
                else
                    sb.append("NO").append("\n");
            }
        }

        System.out.print(sb);
    }

    private static void unionSet(int a, int b) {
        parent[find(b)] = find(a);
    }

    private static int find(int a) {
        if(a != parent[a])
            parent[a] = find(parent[a]);

        return parent[a];
    }
}