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

 

1717번: 집합의 표현

 

 

 

유니온 파인드 개념을 이해하고 적용해볼 수 있는 문제이다. 유니온 파인드 개념은 아래 글을 참고하자.

[알고리즘] 유니온 파인드(Union Find)

 

 

 

유니온 파인드는 그래프에 속하는 두 정점이 연결되어 있는지 판별할 때 사용할 수 있는 알고리즘의 한 종류이다. 이 문제는 유니온 파인드를 구현하면된다. 유니온 파인드는 find와 union 두 연산이 사용되는데 find는 두 요소가 같은 집합에 포함되어 있는지 확인할 때 부모 노드를 반환하는 함수이고 union은 두 요소를 같은 집합에 포함시키는 함수이다.

 

find와 union을 구현하는 방법은 위 링크의 게시글을 만들 때 해보았으므로 이번 문제에 대한 전체 코드만 남기도록 하겠다.

 

 

 

 

 

전체 코드

import java.io.*;

public class Main {
	
	static int[] parent;
	
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        
        parent = new int[n+1];
        for (int i=0; i<=n; i++) parent[i] = i;
        
        
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<M; i++) {
            input = br.readLine().split(" ");
            
            int check = Integer.parseInt(input[0]);
            int a = Integer.parseInt(input[1]);
            int b = Integer.parseInt(input[2]);
            
            
            if (check == 0) 
            	merge(a, b);
            else if (check == 1)
            	sb.append(((find(a) == find(b)) ? "YES" : "NO") + "\n");
            else 
            	continue;
        }
        
        System.out.println(sb);
        
        br.close();
    }
    
    static int find (int num) {
        if (parent[num] == num) return num;
        return parent[num] = find(parent[num]);
    }
    
    static void merge (int a, int b) {
    	
    	a = find(a);
    	b = find(b);
    	
    	if (a != b) {
    		if (a < b) parent[b] = a;
    		else parent[a] = b;
    	}
    }
}