[백준] 1717번 : 집합의 표현 - JAVA [자바]

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

1717번: 집합의 표현

---

문제

 

이 문제는 유니온파인드의 기초문제라고 할 수 있다. 

유니온 파인드를 모른다?! 바로 아래 포스팅을 먼저 보고오자.

https://bean-conding.tistory.com/19

알고리즘 - 유니온파인드, 서로소집합 (Unionfind)

 

서로소 집합에 필요한 연산인 MakeSet, FindSet, Union 메소드를 구현해주고 입력값에 맞게 Union 메소드를 호출하거나 FindSet 메소드를 호출하여 비교하면 끝나는 문제이다.

---

전체 코드

public class Main {
    static int n, m;
    static int[] arr;
    
	public static void main(String[] args) throws Exception {
    	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    	StringBuilder sb = new StringBuilder();
    	StringTokenizer st;
    	
    	st = new StringTokenizer(in.readLine());
    	
    	n = Integer.parseInt(st.nextToken());
    	m = Integer.parseInt(st.nextToken());
    	
    	arr = new int[n + 1];
    	makeSet();
    	
    	for(int c = 0; c < m; c++) {
    		st = new StringTokenizer(in.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){
    			if(findSet(a) == findSet(b)) {
    				sb.append("YES");
    			}
    			else {
    				sb.append("NO");
    			}
    			sb.append("\n");
    		}
    	}
    	
    	System.out.println(sb);
    	
    }
	static void makeSet() {
		for(int i = 0; i <= n; i++) {
			arr[i] = i;
		}
	}
	
	static int findSet(int x) {
		if(x == arr[x]) {
			return x;
		}
		
		return arr[x] = findSet(arr[x]);
	}
	
	static void union(int x, int y) {
		if(x != y) {
			arr[findSet(y)] = findSet(x);
		}
	}
}

---

결과