[백준-JAVA] 1717번 집합의 표현

알고리즘 : 유니온 파인드

 

유니온 파인드는 말그대로 합치기와 탐색입니다.

여기서 상호 배타적인 집합 관계가 나옵니다. 말 그대로 둘이 어떠한 교집합도 없는 집합입니다.

그래프로 생각하면 둘이 완전히 분리된 그래프 인거죠.

 

파인드는 자기 자신의 부모로 계속 올라가서 루트 노드까지 가는 과정이고 

여기에서 만약 서로 다른 두 점을 파인드 했는데 루트 노드가 같을 경우는 이미 같은 집합 인것이고

다를 경우는 다른 집합인 것이겠죠

 

유니온은 말 그대로 두 집합을 합치는 과정인데 여기서 중요한 게 깊이 차이를 신경써야됩니다.

그냥 막무가내로 붙여버리면 깊이가 깊어져서 비효율적이게 됩니다.

그래서 두 루트노드의 랭크를 확인해서 더 큰 랭크인 루트노드를 부모 루트 향하게 작은 랭크의 루트노드를 바꿔주면 트리의 깊이 차가 안생기므로 효율적인 방법이죠.

 

이러한 유니온 파인드를 구현만 한 문제가 1717번입니다.

 

---

문제설명

링크참조

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

 

---

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

class Main{
	private static StringBuilder sb;
	// union 둘의 루트 노드의 랭크를 비교
	// 큰 루트 존재시 : 작은 루트의 부모를 큰 루트 노드로 바꾸고,큰 루트노드 랭크 +1
	// 동일 할 시: 아무쪽으로 붙이고 랭크 +1
	private static void union(int[] arr,int[] rank, int a,int b) {
		int aRoot = find(arr,a);
		int bRoot = find(arr,b);
		if (aRoot == bRoot) {
			return;
		}else {
			if (rank[aRoot] >= rank[bRoot]) {
				rank[aRoot]++;
				arr[bRoot] = aRoot;
			}else {
				rank[bRoot]++;
				arr[aRoot] = bRoot ;
			}
		}
		
	}
	// Find : 같은 집합에 포함되어 있는 지 확인하려면 루트 노드가 같은 지 확인 
	private static int find(int[] arr ,int a) {
		while(arr[a] != a) {
			a = arr[a];
		}
		return a;
	}

	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());
		int[] arr = new int[N+1];
		int[] rank = new int[N+1];
		sb = new StringBuilder();
		// 초기 상태는 전부 자기 자신이 루트 
		for (int i = 0; i <= N; i++) {
			arr[i] = i;
		}
		for (int i= 0; i< M;i++) {
			st = new StringTokenizer(br.readLine());
			int mode = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			if (mode == 0) {
				union(arr,rank,a,b);
			}else {
				if (find(arr,a) == find(arr,b)) sb.append("YES\n");
				else sb.append("NO\n");
			}
		}
		System.out.println(sb);
		
	}
}