[백준/Gold V] 집합의 표현 - 1717

[Gold V] 집합의 표현 - 1717

문제 링크

성능 요약

메모리: 91408 KB, 시간: 3024 ms

분류

자료 구조, 분리 집합

제출 일자

2024년 11월 12일 03:42:39

문제 설명

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

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

입력

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

출력

1로 시작하는 입력에 대해서 $a$와 $b$가 같은 집합에 포함되어 있으면 "YES" 또는 "yes"를, 그렇지 않다면 "NO" 또는 "no"를 한 줄에 하나씩 출력한다.

제출코드

// https://www.acmicpc.net/problem/1717
// [골든래빗] 코딩테스트 합격자 되기 자바편의 347p 문제

import java.io.*;
import java.util.*;

public class Main {
    static int[] arr; // 각 인덱스는 노드 번호(0~n). 값은 집합 노드.

    // union 연산을 수행하는 함수
    static void union(int a, int b){
        arr[a] = a;
        arr[b] = a;
    }

    // 집합의 루트를 찾는 함수
    static int findRoot(int n){
        if(arr[n] == -1 || arr[n] == n){
            return n;
        }
        return findRoot(arr[n]);
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = input[0]; // 최대 노드 번호
        int m = input[1]; // 연산 수

        arr = new int[n+1];
        Arrays.fill(arr,-1); // arr의 값을 -1로 채움.

        StringBuilder sb = new StringBuilder();
        int aRoot, bRoot;
        for (int i = 1; i <= m; i++) {
            input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            aRoot = findRoot(input[1]);
            bRoot = findRoot(input[2]);

            // union 연산
            if(input[0] == 0){
                union(aRoot, bRoot);
            }
            // find 연산
            else{
                if(aRoot == bRoot){
                    sb.append("YES\n");
                }else{
                    sb.append("NO\n");
                }
            }
        }
        br.close();
        System.out.print(sb);
    }
}