문제

집합의 표현 - 골드4

---

문제 이해

유니온 파인드 알고리즘을 이용하여 집합의 표현을 한다.

• 3개의 숫자를 받을 경우 첫번째 숫자가 0이면 유니온 메서드 실행, 1이면 같은 부모에 속해있는지 확인하는 메서드 실행

---

코드

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

public class Baekjoon_1717 {
  static int n;
  static int m;
  static int[] set;

  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());
    set = new int[n + 1];
    for (int i = 0; i < n + 1; i++)
      set[i] = i;
    for (int i = 0; i < m; i++) {
      st = new StringTokenizer(br.readLine());
      int check = Integer.parseInt(st.nextToken());
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      if (check == 1) {
        if (isSameParent(a, b))
          System.out.println("YES");
        else
          System.out.println("NO");
      } else {
        union(a, b);
      }
    }
  }

  public static int find(int x) {
    if (x == set[x])
      return x;
    return set[x] = find(set[x]);
  }

  public static void union(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
      set[y] = x;
    }
  }

  public static boolean isSameParent(int x, int y) {
    x = find(x);
    y = find(y);

    return x == y;
  }

}

---

코드 설명

핵심적인 find(), union(), isSameParent() 메서드에 대해 자세히 설명하고자 한다.

• find 메서드

public static int find(int x) {
  if (x == set[x])
    return x;
  return set[x] = find(set[x]);
}

x가 어떤 집합에 포함되어 있는지 찾는 연산을 수행한다.

• union 메서드

public static void union(int x, int y) {
  x = find(x);
  y = find(y);
  // y가 x보다 크다는 가정하에
  if (x != y) {
    set[y] = x;
  }
}

x와 y가 포함되어 있는 집합을 합치는 연산을 수행한다.

• isSampeParent 메서드

public static boolean isSameParent(int x, int y) {
  x = find(x);
  y = find(y);

  return x == y;
}

같은 부모를 가르키고 있는지 확인하는 연산을 수행한다.

알고리즘 스터디 시간에 팀원분께서 너무 자세하게 설명해주셔서 쉽게 이해할 수 있었다.

---