이번에 풀어본 문제는
백준 1717번 집합의 표현 입니다.

📕 문제 링크

❗️코드

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

public class Main {
    static int [] parents;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        parents = new int[n+1];
        for(int i = 0; i <= n; ++i) parents[i] = i; // 자기자신을 부모로 초기화

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < m; ++i)
        {
            st = new StringTokenizer(br.readLine());
            int cmd = Integer.parseInt(st.nextToken());
            int fst = Integer.parseInt(st.nextToken());
            int sec = Integer.parseInt(st.nextToken());

            if(cmd > 0) sb.append(getParent(fst) == getParent(sec) ? "YES" : "NO").append("\n");
            else setParent(fst,sec);
        }
        System.out.print(sb);
    }
    static int getParent(int child)
    {
        if(parents[child] == child) return child;
        return getParent(parents[child]);
    }
    static void setParent(int fst, int sec)
    {
        int a = getParent(fst);
        int b = getParent(sec);

        if(a > b) parents[b] = a;
        else if(a < b) parents[a] = b;
    }
}

📝 풀이

연산으로 0과 1이 주어집니다. 0은 합집합 연산, 1은 두 수가 같은 집합에 속해있는지 판단하여 yes or no를 출력하는 연산입니다.
0의 연산이 들어왔을 때, setParent 함수에서 한 노드를 부모로 설정해주며, 편의상 작은 숫자를 부모로 두었습니다. 1의 연산이 들어왔을 때는, 현재 상태에서 두 노드의 부모노드가 같은지 여부를 판단하여 결과를 Stringbuilder에 담아줍니다.
기본적인 유니온파인드 문제였습니다.

📜 후기

뭔가 오랜만에 마주한 유니온 파인드 문제였지만, 다행히 보자마자 기억이 나서 쉽게 풀었던 것 같습니다. 겸사겸사 복습한 것 같아서 좋네요!