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

백준 1717번 문제 - 집합의 표현 

1717번: 집합의 표현

---

문제 분석

 

• N개의 수가 주어지면 N개는 각각 다른 집합으로 구성된다.
• M개의 수식이 주어지며, 수식은 다음 2가지 종류가 있다.
  • 0 a b : b 집합을 a 집합에 포함 시킨다.
  • 1 a b : a와 b가 동일한 집합이면 YES, 아니면 NO 출력

---

 

해결 키 포인트

 

• 유니온 파인드(union-find) 개념 사용
• 0도 포함되므로 배열 구현할 때, N개 배열 생성하고 a,b에서 -1을 하면 안된다. N+1개 배열 생성!

---

유니온 파인트 (union-find)

여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지 확인하는 find 연산으로 구성되어 있는 알고리즘이다.

 

• union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산이다. 노드 a, b가 a ∈ A, b ∈ B일 때 union(a, b)는 A∪B를 말한다.
• find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산이다. 노드 a, b가 a ∈ A일 때 find(a)는 A 집합의 대표 노드를 반환한다. 

 

Union 연산 알고리즘

• 1차원 배열을 이용해서, i번째 값은 i로 변수 초기화한다. ( 대표 노드는 본인 )
• union(a, b) 연산은 a와 b의 대표 노드를 알아내 'b 대표 노드'의 value( list['b 대표 노드'] )을 'a 대표 노드'로 변경한다.
  • index == list[index] : 해당 index가 집합의 대표 노드
    index !=  list[index] : 대표 노드를 알아내야 함 ( 배열의 list[index]와 list[list[index]] 비교 )
  • list['b 대표 노드'] = 'a 대표 노드' 로 b 집합을 a 집합에 포함시킨다.

 

Find 연산 알고리즘

• 대상 노드 배열에 index 값과 value 값이 동일한지 확인
• 동일하지 않으면 value 값이 가리키는 index 위치로 이동
• 이동 위치의 index 값과 value 값이 같을 때까지 앞 방법들을 반복 (재귀함수로)
• 대표 노드에 도달하면 재귀함수를 빠져나오면서 거치는 모든 노드 값을 대표 노드 값으로 변경

---

코드

import java.io.*;
import java.util.*;

public class Main {
    public static int [] collection;
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // n,m 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // N개의 집합 생성
        collection = new int [N+1];
        for(int i=0;i<=N;i++) {
            collection[i] = i;
        }

        // M개의 연산 실행
        for(int i=0;i<M;i++) {
            // 연산 종류(0: union, 1: find) a b 입력
            st = new StringTokenizer(br.readLine());
            int operator = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            // operator가 0 일 때 : a,b 집합 합치기 : a,b union
            if(operator == 0) {
                union(a, b);
            }

            // operator가 1 일 때 : a와 b가 같은 그룹인지 확인 : find
            if(operator == 1) {
                if (find(a) == find(b))
                    bw.write("YES\n"); // 같은 그룹일 경우 yes 출력
                else
                    bw.write("NO\n");  // 아닐 경우 no 출력
            }
        }
        bw.flush();
        bw.close();
    }

    public static void union(int a, int b) {
        int firstA = a, firstB = b;

        // a가 집합 대표가 아닐 경우 (a와 collection[a]가 동일 하지 않을 경우)
        if(a != collection[a])
            firstA = find(a); //  a 집합 대표 찾기 ( find(a) )


        // b가 집합 대표가 아닐 경우 (b와 collection[b]가 동일 하지 않을 경우)
        if(b != collection[b])
            firstB = find(b); //  b 집합 대표 찾기 ( find(b) )

        // b 집합의 대표를 a 집합의 대표로
        collection[firstB] = firstA;
    }

    public static int find(int a) {
        // a가 집합 대표일 경우 (a와 collection[a]가 동일 할 경우)
        if (a == collection[a])
            return a;

        //  a가 집합 대표가 아닐 경우
        collection[a] = find(collection[a]);
        return collection[a];
    }
}