[백준/자바] 1717 : 집합의 표현

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

1717번: 집합의 표현

---

Union Find의 기초문제이다.

이 문제를 통해 처음으로 Union Find 알고리즘을 공부하였다.

예시 코드가 자바는 아니지만 다음 글이 큰 도움이 되었다 👍

https://4legs-study.tistory.com/94

분리 집합 (Disjoint Set) : Union-Find

 

풀이과정은 다음과 같다.

 

• 입력이 0으로 시작하면 union을 통해 두 집합 합치기
• 입력이 1으로 시작하면 find를 통해 최상위 노드값이 같은지 확인하기

public class Main {

   public static int[] set;

   public static void main(String[] args) throws IOException {
       // TODO Auto-generated method stub
       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());
       set = new int[N + 1];
      for (int i = 0; i <= N; i++) {
           set[i] = i;
       }

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

           if (cmd == 0) {
               union(a, b);
           } else {
               sb.append(find(a) == find(b) ? "yes" : "no").append("\n");
           }
       }
       System.out.println(sb);
   }

   public static int find(int x) {
       if (set[x] == 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) {
          if (x > y)
               set[y] = x;
           else
               set[x] = y;
       }
   }
}

특히, find 함수에서 set[x] = find(set[x]) 부분과 union에서 x,y의 대소 비교 하는 부분은

연산을 더 효율적으로 하기 위해(최적화) 추가된 부분이다.