문제 이해

1차 코드

/*
 * 2025-06-26
 * 문제50_백준 1717번
 * */

package day8.B1717;

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

public class Main {
    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());

        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int zor = Integer.parseInt(st.nextToken()); //zero or one
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
        } // 여기까지 입력받고

        // 여기서 zor이 0이면 union 호출, 1이면  find 호출할 예정.

    }
    /***/
    static void union(int[] a, int[]b){
        int lenC = a.length + b.length;
        int[] c = new int[lenC]; // 새로운 배열

        for(int i = 0; i < lenC; i++){
            Arrays.copy(c, a);

        }
    }

    /***/
    static void find(){

    }
}

❌ 현 코드의 문제점

지금 union 부분은 a 집합과 b 집합을 배열로 만들어 합치겠다.(c 배열) 인데,

본질적으로 틀린 이유가 있다. 3가지 이유

1. 문제의 목적은 “집합 전체 구성원” 이 아니라 “대표자” 만 알면 된다.
   • union-find는 집합 내부 배열을 따로 돌지 않는다.
   • 어떤 원소 x 가 속한 집합의 대표만 추적하면 된다.
   • find(x)는 그 루트를 찾고
   • union(x,y)는 둘의 루트를 같게 만들어주는 구조이다.

→ 따라서 배열을 복사해서 전체 원소를 관리할 필요가 없다.

1. 효율성 문제 : 배열 합치면 시공간 둘 다 비효율
   • 배열 합칠 때 o(n) + 새로운 배열 할당 o(n)
   • 유니온-파인드는 거의 o(1) 보장
2. union-find는 동적 집합 연결문제를 위한 자료구조다
   • 이 문제는 같은 집합인지 판별하는 게 목적이다.
   • a,b가 같은 집합에 있는지 o(1) 안에 판단해야 한다.
   • 근데 배열 합치기는 비교, 탐색, 업뎃 모두 o(n)이다.

Q) 근데 그럼 이 문제만 읽고 어떻게 배열 합치기가 아니라 union-find 유형인지 알아?

왜냐, 이 문제는 아래 두 연산을 반복한다.

1. 합집합 2. 포함 여부

이 두 연산이 반복되는 문제 = union-find pattern이다.

“초기에 {0}, {1}, ..., {n}의 n+1개의 집합이 있다” → 이는 서로소 집합 구조임을 알려준다.