[백준] 1717번 집합의 표현

문제 설명

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작성하시오.

입력

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작성하시오.

출력

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

풀이 방법

1. parent[i]를 초기화
2. Union - a,b를 같은 집합으로 합침
3. find - a 그룹에 포함된 모든 정점을 b와 같은 그룹으로 만들기 위해서 사용
   
   
   
   

📝 java code

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

// 유니온 파인드, 서로소 집합
public class Main {
	static int[] parent;
	static int N, M;
	static int val,a,b;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		
		// 초기화
		parent = new int[N+1];
		for(int i=1; i<=N; i++)
			parent[i] = i;
		
		M = Integer.parseInt(st.nextToken());
		
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			
			val = Integer.parseInt(st.nextToken());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			
			if(val == 0) { // 합집합
				Union(a,b);
			} else if(val == 1) {
				// 같은 집합인지 확인하는 경우 - Find
				if(find(a) == find(b))
					sb.append("YES\n");
				else
					sb.append("NO\n");
			}
		}
		System.out.println(sb.toString());
	}

	static int find(int a) {
		if(parent[a] == a)
			return a;
		return parent[a] = find(parent[a]);
	}
	
	static void Union(int a, int b) {
		int pa = find(a);
		int pb = find(b);
		
		// a 그룹에 포함된 모든 정점을 b와 같은 그룹으로 만들기 위해서
		parent[pa] = pb;
	}
}

🤔 개인적인 의견

Union과 find는 많이 사용되므로 중요하다!