잼있다 하하

문제링크

백준 #1717. 집합의 표현

풀이방법

유니온파인드 연습문제다! 이 사실을 몰라도 문제 내에서 구현이 필요한 연산이 집합합치기/같은집합여부->루트찾기 이고 겹치는 원소가 없는 disjoint 성격이 있기 때문에 쉽게 유니온파인드 사용을 결정할 수 있다.

간단한 유니온파인드 구현문제이긴 하지만 find 연산과 union 연산 구현을 설명하자면 다음과 같다.

• find 연산 구현
  일단 집합(tree)의 루트를 찾는 것을 목표로 한다. 루트를 의미하는 -1 값을 이용했다. 그리고 주욱 늘어진 구조의 경우 시간측면에서 불리하고 루트를 찾는 간단한 연산만 필요하므로 루트를 찾으면 바로 해당 원소를 루트 밑으로 달아준다!

• union 연산 구현
  두 원소가 같은 집합에 속하는지 확인한다.(각각의 루트를 구하고 비교) 다른 집합에 속한다면, 한 원소가 속한 집합을 다른 원소의 밑으로 달아준다! easy!

코드

import java.util.Scanner;

public class RepresentingSet {
    static final int ROOT = -1;
    static int[] p;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

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

        StringBuilder result = new StringBuilder();
        while( m-- > 0) {
            int op = sc.nextInt();
            int a = sc.nextInt();
            int b = sc.nextInt();

            if (op == 0) {
                merge(a, b);
            } else {
                if (find(a) == find(b)) result.append("YES\n");
                else result.append("NO\n");
            }
        }

        System.out.print(result.toString());
    }

    private static int find(int n) {
        if (p[n] == ROOT) return n;
        else {
            p[n] = find(p[n]);
            return p[n];
        }
    }

    private static void merge(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);

        if (aRoot != bRoot) p[bRoot] = a;
    }
}

🤓🤓