b1717. 집합의 표현

 

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

 

 

 

🧩 자바로 푸는 집합의 표현 문제 풀이

 

---

 

📌 문제 개요

 

백준 1717번 집합의 표현 문제는 Disjoint Set(서로소 집합) 자료구조의 기본 동작인 Find와 Union을 구현하는 대표적인 문제입니다.

 

• 연산 종류
  • 0 a b : a와 b가 속한 집합을 합친다.
  • 1 a b : a와 b가 같은 집합에 포함되어 있는지 확인한다.
•  

 

---

 

💡 예제 입력

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

예제 출력:

NO
NO
YES

 

 

---

 

🧠 알고리즘 접근 방식

 

• 핵심은 Union-Find 알고리즘입니다.
• 각 원소는 자신이 속한 집합의 대표(parent)를 가리킵니다.
• find(x)를 통해 대표를 찾고, union(x, y)를 통해 두 집합을 병합합니다.
• find에는 **경로 압축(Path Compression)**을 적용해 시간 복잡도를 줄입니다.

 

---

 

🧾 코드 해설

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

public class Main {
    static int n, m;
    static int[] parent;

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

        for (int i = 0; i <= n; i++) parent[i] = i;

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int op = Integer.parseInt(st.nextToken());
            int a  = Integer.parseInt(st.nextToken());
            int b  = Integer.parseInt(st.nextToken());

            if (op == 0) {
                union(a, b);
            } else {
                sb.append(find(a) == find(b) ? "YES\n" : "NO\n");
            }
        }

        System.out.print(sb);
    }

    static int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) parent[rootB] = rootA;
    }
}

✔ find 함수는 경로 압축을 이용해 부모를 재귀적으로 최상위 루트로 갱신합니다.

✔ union 함수는 두 원소의 루트를 찾아서 병합합니다.

✔ 입력이 많기 때문에 BufferedReader와 StringBuilder를 사용하여 입출력 성능을 최적화합니다.

 

---

 

🎯 결론

 

이 문제는 Union-Find 알고리즘을 연습하기에 가장 적합한 문제입니다.

특히 경로 압축 없이 풀면 시간 초과가 발생하므로, find()에 꼭 최적화를 적용해야 합니다.

 

👉🏼 서로소 집합 문제를 풀 때는 항상 다음 두 가지를 염두에 두자:

 

1. find()에는 경로 압축을!
2. union()에는 대표노드 병합을!