[백준/Java] 1717 집합의 표현 : 유니온 파인드

---

1) union 연산

- 각 노드가 속한 집합을 1개로 합치는 연산이다. 노드 a, b가 a ∈ A, b ∈ B일 때 union(a, b)는 A ∪ B를 말한다.

2) find 연산

- 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산이다. 노드 a가 a ∈ A일 때 find(a)는 A 집합의 대표 노드를 반환한다.

- 그래프를 정돈하고 시간 복잡도를 향상시킨다.

 

- find 연산의 작동 원리

1) 대상 노드 배열에 index와 value 값이 동일한지 확인

2) 동일하지 않으면 value 값이 가리키는 index 위치로 이동

3) 이동 위치의 index 값과 value 값이 같을 때까지 1~2번 반복, 반복이므로 이 부분은 재귀 함수로 구현

4) 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 루트 노드값으로 변경

import java.util.*;

public class Main {
    public static int arr[];

	public static void main(String[] args) {	// 유니온 파인드
		
		Scanner sc = new Scanner(System.in);
		
		int n1 = sc.nextInt();	// 원소 개수
		int n2 = sc.nextInt();	// 질의 개수
		
		arr = new int[n1 + 1];
		
		for (int i = 1; i < arr.length; i++) {
			arr[i] = i;
		}
		
		for (int i = 0; i < n2; i++) {
			int q = sc.nextInt();
			int x = sc.nextInt();
			int y = sc.nextInt();
			if (q == 0) {
				unione(x,y);
			} else if (q == 1) {
				System.out.println(checkSame(x, y) ? "YES" : "NO");
			}
		}
		
		sc.close();
	}
	
	public static void unione(int x, int y) {	// union 연산 : 대표 노드끼리 연결
		x = find(x);	// 대표 노드 찾음
		y = find(y);	// 대표 노드 찾음
		if (x != y) {
			arr[y] = x;
		}
	}
	
	public static int find(int v) {		// find 연산 : 매개변수가 속한 집단의 대표 노드 반환
		if (arr[v] == v) {
			return v;
		} else {
			return arr[v] = find(arr[v]);	// 재귀 함수의 형태로 구현 -> 경로 압축 부문
		}
	}
	
	public static boolean checkSame(int x, int y) {	// 대표 노드 같으면 true, 다르면 false (두 원소가 같은 집합인지 확인)
		x = find(x);
		y = find(y);
		
		if (x == y)
			return true;
		else
			return false;
	}
}