[백준 문제 풀기] 1717번: 집합의 표현 (Disjoint-set, 자바)

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

 

문제
초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력
첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

출력
1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

 

예제 입력, 출력

	예제 입력	예제 출력
1	7 8 0 1 3 1 1 7 0 7 6 1 7 1 0 3 7 0 4 2 0 1 1 1 1 1	NO NO YES

 

사용 알고리즘

Disjoint-set

 

코드 (자바)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 집합의 표현 : https://www.acmicpc.net/problem/1717
// Disjoint-set (union, find)


public class Main {
	
	static int N = 0;	// 숫자의 개수 (1≤n≤1,000,000)
	static int M = 0;	// 연산의 개수 (1≤m≤100,000)
	static int[] parent;	// 집합 배열
	
	static int find(int num) {
		if (num == parent[num]) {
			return num;		// 부모와 입력값이 같으면 자신이 부모
		} else {
			return parent[num] = find(parent[num]);	//부모의 노드값을 리턴. 빠른 처리를 위해 재귀 호출을 통한 최상위 부모 값으로 업데이트 
		}
		
	}
	
	static boolean union (int a, int b) {
		int parentA = find(a);
		int parentB = find(b);
		
		if (parentA == parentB) {	// 부모가 같다면 같은 집합이므로 union 을 하지 않음. 그래서 false 리턴
			return false;
		} else {
			parent[parentB] = parent[parentA];
			
			return true;
		}
		
	}
	
	
	public static void main(String[] args) throws Exception{
		// 입력값 처리
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		parent = new int[N+1];	// parent 배열 생성
		// parent 배열 초기화. (각각의 값이 부모 노드로 초기화)
		for (int i=1 ; i<=N ; i++) {
			parent[i] = i;
		}
		
		for (int i=1 ; i<=M ; i++) {
			st = new StringTokenizer(br.readLine());
			int type = Integer.parseInt(st.nextToken());	// 0 : a, b 를 합침, 1 : a, b 가 같은 집합에 포함되어있는지의 여부
			int a = Integer.parseInt(st.nextToken());		// a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.
			int b = Integer.parseInt(st.nextToken());
			
			if (type == 0) {	// a, b 를 합침
				union (a, b);
				
				
			} else {			// a, b 가 같은 집합에 포함되어있는가?
				if (find(a) == find(b)) {
					System.out.println("YES");
				} else {
					System.out.println("NO");
				}
			}
			
		}
	}
}