[백준] 1717 - 집합의 표현 | Java

짱챌·2025년 4월 18일

DataStructures UnionFind 백준

Algorithm

목록 보기

9/19

📌 문제 정보

[1717번: 집합의 표현]

💡 접근 방식

같은 집합에 속한다라는 의미를 정리해보겠다.

유니온

0 1 2 -> 1과 2는 같은 집합
0 2 3 -> 1, 2, 3은 같은 집합
0 4 5 -> 4, 5는 같은 집합 ( 1, 2, 3 집합과는 별개 )

set

0 1 2 -> 1과 2는 같은 집합
0 2 3 -> 1, 2, 3은 같은 집합
0 4 5 -> 1, 2, 3, 4, 5는 같은 집합

그럼 이제 해당 값들이 같은 집합에 속하는 지는 어떻게 알 수 있을까?
주어진 값들의 연결 관계를 설정해야 한다.

0 1 2에서 2의 루트(부모)를 1로 둔다면,
0 2 3에서 3의 루트는 2가 되고,
0 3 4에서 4의 루트는 3이 된다.

이를 압축하여 정리하면,
1, 2, 3, 4의 루트는 모두 1이라고 볼 수 있다! (트리 구조)

초기에는 0 ~ n 까지의 수의 루트를 자기 자신으로 설정한다.

유니온 연산을 수행하면서, 주어진 두 수의 루트가 다르면 루트를 연결하면 된다.

find는 루트를 찾아가면서 중간 노드들도 루트에 직접 연결해 트리 깊이를 줄여준다.
이렇게 하면 나중의 find 연산이 더 빠르게 동작한다! -> 경로 압축

유니온 파인드는 각 원소가 속한 집합의 루트(부모)를 관리한다.
초기의 모든 노드는 자기 자신을 루트로 가진다.
이후 union(a, b) 연산을 통해 두 노드의 루트를 찾아 하나로 합치고,
find(x) 연산을 통해 어떤 노드가 어떤 집합에 속해 있는지를 확인할 수 있다.

🧪 시도한 풀이

틀림... 당연함....


import java.util.*;

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

public class Main {
    public static void main(String[] args) throws NumberFormatException, 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());

        StringBuilder sb = new StringBuilder();

        List<Integer> aList = new ArrayList<>();
        List<Integer> bList = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int option = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if (option == 0) {
                aList.add(a);
                bList.add(b);

            } else {
                if (aList.contains(a) && bList.contains(b)) {
                    sb.append("YES").append("\n");
                } else {

                    sb.append("NO").append("\n");
                }
            }
        }

        System.out.println(sb);
    }
}

🔍
set과 union의 차이를 이해하지 못하고 푼 코드이다. 이는 단순히 어떤 수가 등장했었는가만을 판별하고 있었다!

✅ 코드

import java.util.*;

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

public class Main {
    static int[] root;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        root = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            root[i] = i;
        }

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

            if (option == 0) {
                union(a, b);

            } else {
                if (find(a) == find(b)) {
                    sb.append("YES").append("\n");
                } else {

                    sb.append("NO").append("\n");
                }
            }
        }

        System.out.println(sb);
    }

    public static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        if (rootA != rootB) {
            root[rootB] = rootA;
        }
    }

    public static int find(int x) {
        if (root[x] != x) {
            root[x] = find(root[x]);
        }

        return root[x];
    }
}

🧠 배운 점 & 회고

같은 집합에 속한다라는 개념이 이해가 안돼서 좀 헤맸다..
set에 넣으면 같은 집합에 속하는 거 아닌가???
심지어 문제 자체를 잘못 이해해서 ~~난독인가?~~ a와 b를 다른 집합으로 저장하고 있었다. 문제를 풀면서도 n이 도대체 왜 주어졌는가는 의문은 있었지만,
종종 문제를 풀다 보면 주어진 입력을 사용하지 않고도 풀리는 경우가 있었어서.. 대수롭지 않게 넘겼던 것 같다.