[백준 - 1717번] 집합의 표현 - Java //Wello Horld//

이번에는 BOJ의 1717번 문제 "집합의 표현"를 풀어보도록 하자

문제를 풀어서 설명해 보면, 입력으로 맨처음에 주어지는 원소들의 총 크기, n 이 주어지고, 연산의 개수 m이 주어진다. 연산중에서 "0 a b"의 형태로 주어지는 것은 합집합으로, a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합치는 연산이다. 그리고, "1 a b"의 형태로 주어지는 연산은 확인하는 연산으로, 두 원소 a b가 같은 집합에 포함되어 있는지를 확인해서 포함되어 있으면, "YES"를 아니면 "NO"를 출력하는 문제이다.

가장 기본적인 디스조인트셋(Disjoint-set)문제이다. 이런 문제는 기본적으로, 초기에 set을 만들어주는

• makeset

public static void makeSet(int n){
    parent = new int[n + 1];
    for(int i = 0; i <= n; i++){
        parent[i] = i;
    }
}

• merge(합병)

public static void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) {
        return;
    }
    parent[a] = b;
}

• find

public static int find(int a) {
    if (a == parent[a]) {
        return a;
    }
    return parent[a] = find(parent[a]);
}

를 통해, 문제를 풀어주면 된다.

성공한 코드는 아래와 같다.

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

public class sample {
	static int[] parent;
    public static void main(String[] args) throws Exception {
        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());

        makeSet(n);

        for(int i = 0; i < m; i ++){
            st = new StringTokenizer(br.readLine());
            int san = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            if(san == 0){
                merge(a, b);
            } else if(san == 1) {
                a = find(a);
                b = find(b);
                if(a == b){
                    bw.write("YES\n");
                } else {
                    bw.write("NO\n");
                }
            }
        }

        bw.flush();
        br.close();
        bw.close();
    }
    public static void makeSet(int n){
        parent = new int[n + 1];
        for(int i = 0; i <= n; i++){
            parent[i] = i;
        }
    }
    public static void merge(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b) {
			return;
		}
		parent[a] = b;
	}
	public static int find(int a) {
		if (a == parent[a]) {
			return a;
		}
		return parent[a] = find(parent[a]);
	}

}

 

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

1717번: 집합의 표현