BOJ_1717 : 집합의 표현

👉 문제링크

1717번: 집합의 표현

---

---

🔸 문제 분석 🔸

• 0부터 n까지 원소가 1개씩 들어있는 n+1개의 집합에서 입력 연산의 결과를 출력한다.
  • 0은 두 집합의 합집합 연산을 수행한다.
  • 1은 두 집합이 같은 집합인지 확인해, 같으면 "YES" 혹은 "yes", 다르면 "NO" 혹은 "no"를 출력한다.
• 전형적인 union-find 알고리즘 문제이다.
  • 합집합 연산은 union을 사용한다.
  • 두 집합이 같은 집합인지 확인은 find를 사용해 반환값을 비교한다.

🔸 코드 🔸

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

public class Main {
    private 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;
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            if (Integer.parseInt(st.nextToken()) == 0) union(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            else if (find(Integer.parseInt(st.nextToken())) == find(Integer.parseInt(st.nextToken())))
                System.out.println("YES");
            else
                System.out.println("NO");
        }
    }

    private static int find(int n) {
        if (parents[n] == n) return n;
        return parents[n] = find(parents[n]);
    }
    private static boolean union(int n1, int n2) {
        int p1 = find(n1);
        int p2 = find(n2);

        if(p1 == p2) return false;

        parents[p2] = p1;
        return true;
    }
}

🔸 코드 해석 🔸

• make-set() 메서드는 따로 만들지 않고 paretns배열을 main에서 초기화했다.
• 입력 연산이 0일 경우는 각 원소가 들어있는 두 집합을 union 한다.
• 입력 연산이 1일 경우는 각 원소를 find 연산 후 반환값을 비교한다.
  • 두 반환값이 같으면 "YES"를 출력한다.
  • 두 반환값이 다르면 "NO"를 출력한다.

---

🔸 end 🔸

• union-find 알고리즘을 알고 문제를 보니, 아주 쉽게 풀이할 수 있었다.