백준 1717 (집합의 표현)

문제

---

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

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

 

 

 

 

 

 

풀이

---

Union-Find 문제의 가장 기본이 되는 문제다.

 

3가지 함수가 필요하다

◎ Find(x)

  ▶ 찾기

  ▶ x가 속한 집합의 대표값(루트 노드 값)을 반환한다.

 

◎ Union(x, y)

  ▶ 합하기(합집합)

  ▶ x가 속한 집합과 y가 속한 집합을 합니다. 

  ▶ x < y 이면 x 의 부모가 y 의 부모가 된다. parent[y] = x (반대는 반대로)

 

◎ isSameParent(x, y)

  ▶ 비교(교집합)

  ▶ x 와 y 의 부모가 같은지 확인

 

 

<전체 코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {	
	
	static StringBuilder sb = new StringBuilder();
	static int[] parent;
	
	public static void main(String[] args) throws IOException{
		
	    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
	    
	    StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
	    
	    int n = Integer.parseInt(st.nextToken());
	    int m = Integer.parseInt(st.nextToken());
	    
	    parent = new int[n+1];
	    for(int i = 0 ; i <= n ; i++) {
	    	parent[i] = i;
	    }
	    
	    for(int i = 0 ; i < m ; i++) {
	    	st = new StringTokenizer(bufferedReader.readLine());
	    	int command = Integer.parseInt(st.nextToken());
	    	int a = Integer.parseInt(st.nextToken());
	    	int b = Integer.parseInt(st.nextToken());
	    	
	    	if(command == 0) {
	    		union(a, b);
	    	}
	    	else if(command == 1) {
	    		sb.append((isSameParent(a, b) ? "YES" : "NO") + "\n");
	    	}
	    	else {
	    		continue;
	    	}
	    }
	        
	    System.out.println(sb);
	}
	
	//x의 부모를 찾는 연산
	public static int find(int x) {
		if(x == parent[x])
			return x;
		
		return parent[x] = find(parent[x]);
	}
	
	// y의 부모를 x의 부모로 치환하는 연산 (x > y 일 경우, 반대)
	public static void union(int x, int y) {
		x = find(x);
		y = find(y);
		
		if(x != y) {
			if(x < y) {
				parent[y] = x;
			}
			else {
				parent[x] = y;
			}
		}
	}
	
	
	public static boolean isSameParent(int x, int y) {
		x = find(x);
		y = find(y);
		
		if(x == y) {
			return true;
		}
		else
			return false;
	}
}