[백준] 1717번. 집합의 표현(JAVA)

문제

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

---

풀이(17분)

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;

        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;
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int flag = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            if (flag == 0) {
                union(x, y);
            } else {
                if (find(x) == find(y)) { // find 호출로 부모 확인
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            }
        }
    }

    // Union 연산
    public static void union(int x, int y) {
        x = find(x);
        y = find(y);

        if (x != y) { // 이미 같은 집합이 아닐 때만 병합
            if (x < y) {
                parent[y] = x;
            } else {
                parent[x] = y;
            }
        }
    }

    // Find 연산 (경로 압축 포함)
    public static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 경로 압축
        }
        return parent[x];
    }
}

 

문제 속의 합집합이라는 단어를 통해 union-find 알고리즘이란는 것을 알아낼 수 있었다면 그 자체로 어려운 문제는 아니었다.

 

즉, 이 문제는 유니온 파인드 알고리즘을 본인의 것으로 채화하여 활용할 수 있는 것이냐를 묻는 문제였다.

 

union-find 알고리즘을 모른다면 꼭 공부하자!!

 

코드가 이해되지 않거나, 알고리즘에 대해 어려운 부분이 있다면 https://to-travel-coding.tistory.com/215 링크를 참고하자. 다음 문제를 통해 union-find를 설명해두었다!