[BOJ] 1717 집합의 표현 Java 풀이

 

BOJ 1717 집합의 표현

 

그래프 이론 중 Union & Find 개념을 알고 있다면 쉽게 접근할 수 있는 문제다. 합집합 연산에서는 Union, 같은 집합에 포함되어 있는지 확인 연산은 Find로 확인할 수 있다.

기본적으로 단일 Union&Find 연산에서 시간 복잡도는 O(N)인데, 그런 연산이 이 문제에서는 M번 주어지므로, 단순하게 Union & Find를 구현하게 되면 시간초과를 볼 수 있는데, 경로압축기법을 사용해 시간복잡도를 대폭 단축시키면 대략 O(M)번의 연산으로 이 문제를 해결할 수 있다.

 

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

public class Main {
	static int N, M;
	static int[] parents;
	
	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());
		
		parents = new int[N+1];
		for(int i = 0; i <= N; i++) {
			parents[i] = i;
		}
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int func = Integer.parseInt(st.nextToken());
			int n1 = Integer.parseInt(st.nextToken());
			int n2 = Integer.parseInt(st.nextToken());
			
			if(func == 0) {
				parentUnion(n1, n2);
			}else {
				if(parentFind(n1) == parentFind(n2)) {
					System.out.println("YES");
				}
				else {
					System.out.println("NO");
				}
			}
		}
	}
	
	private static int parentFind(int a) {
		if(parents[a] != a) {
			parents[a] = parentFind(parents[a]);
		}
		return parents[a];
	}
	
	private static void parentUnion(int a, int b) {
		a = parentFind(a);
		b = parentFind(b);
		if(a < b) {
			parents[b] = a;
		}else {
			parents[a] = b;
		}
	}
}