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

문제

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

1717번: 집합의 표현

풀이

서로소 집합을 사용한다.

서로소 집합은 공집합인 집합(서로소) 들의 정보를 확인(find)하고 조작(union)할수 있는 자료구조다.

union 연산은 두 원소 a, b에 대하여 두 원소가 속한 집합을 하나로 합치는 집합이다.

find 연산은 a가 속한 집합의 대표번호를 반환한다.

따라서 union 연산을 할때에는 두 원소의 대표번호를 변경하면 된다.

 

-초기화

배열에 i 원소에 대한 부모 노드 번호를 저장한다. 루트 노드인 경우 자기 자신의 번호를 저장한다.

 

-union

하나의 루트 노드를 다른 하나의 루트 노드의 자식으로 넣어  두 트리로 합친다. 즉, 대표 번호를 변경한다.

 

-find

주어진 원소의 대표번호를 반환한다.

 

항상 유념해야 할것은 루트 노드의 대표 번호는 루트노드의 index 번호라는 것이다.

 

코드

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

public class Main {	 
	
	static int arr[];
	
	public static void main(String[] args) throws Exception {
		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());
		
		arr = new int [n+1];
		
		for(int i=1;i<=n;i++) {
			arr[i] = i;
		}
		
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			if(a == 0) {
				union(b,c);
			}
			else if(a == 1) {
				int aRoot = findRoot(b);
				int bRoot = findRoot(c);
				if(aRoot == bRoot)
					sb.append("YES");
				else
					sb.append("NO");
				sb.append("\n");
			}
		}
		
		System.out.println(sb);
		
	}

	static void union(int a, int b) {
		int aRoot = findRoot(a);
		int bRoot = findRoot(b);
		arr[bRoot] = aRoot;
	}
	
	static int findRoot(int a) {
		if(arr[a] == a)
			return a;
		else
			return arr[a] = findRoot(arr[a]);
	}
	
}