[BOJ][Java] 백준 1717번: 집합의 표현

문제 설명

초기에 {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이며 같을 수도 있다.

문제 풀이

이 문제의 핵심은 유니온 파인드 입니다. 아래 블로그를 통해 유니온 파인드의 개념을 읽어보시는걸 추천드립니다.

[Algorithm] 유니온 파인드(Union - Find)

쉽게 정리하면 유니온 파인드는 각 노드마다 최상단의 부모를 설정해주는 작업입니다.

 

처음 parent배열은 parent[i] = i 형태로 자기 자신을 가리킵니다.

 

이제 조건에 따라 0일 때는 합집합(union)을 1일 때는 교집합의 여부(compare)를 비교해주면 됩니다.

 

풀이 코드

package BOJ.p1700;

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

public class BOJ1717 {
    private static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        parent = new int[N+1];
        for(int i=1; i<=N; i++) parent[i] = i;

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int type = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if (type == 0) {
                union(arr, a, b);
            } else {
                sb.append(compare(a, b) ? "YES" : "NO").append('\n');
            }
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    private static int find(int n){
        if(parent[n] == n) return n;
        return parent[n] = find(parent[n]);
    }

    private static void union(int x, int y){
        x = find(x);
        y = find(y);

        if(x != y){
            if(x < y) parent[y] = x;
            else parent[x] = y;
        }
    }

    private static boolean compare(int x, int y){
        return find(x) == find(y);
    }
}

 

<출처>https://www.acmicpc.net/problem/1717

1717번: 집합의 표현