백준 1717번(집합의 표현)[JAVA]

풀이

유니온 파인드 문제이다. 유니온 파인드(Union-find)란, 여러 노드가 있을 때 특정 2개의 노드를 연결하여 하나의 집합을 묶는 union연산, 특정 노드가 속한 집합의 대표 노드를 찾는 find연산으로 이루어져 있다.
union연산은 인덱스와 값이 같게 초기화된 배열에서 union된 두 노드 중 하나 인덱스의 값을 다른 노드 인덱스의 값(일명 대표 노드)으로 바꿔주면 끝이다. find는 특정 노드의 대표 노드를 찾으면 바로 그 값을 리턴하고, 아니라면 대표 노드를 재귀 호출로 계속 찾아낸다.
즉, 이 문제에서는 0 연산은 두 숫자를 union한다는 의미이고, 1은 두 숫자를 각각 find하여 find한 값(대표 노드)들이 같은지 확인하는 것이다.

소스 코드

import java.util.*;

public class 집합의표현 {
	static int[] arr;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		arr = new int[n+1];
		for (int i = 1; i < n+1; i++) {
			arr[i] = i;
		}
		
		for (int i = 0; i < m; i++) {
			int command = sc.nextInt();
			int a = sc.nextInt();
			int b = sc.nextInt();
			
			if (command == 0) {
				union(a,b);
			} else {
				if (find(a) == find(b)) {
					System.out.println("YES");
				} else {
					System.out.println("NO");
				}
			}
		}
	}
	
	static void union(int x, int y) {
		x = find(x);
		y = find(y);
		if (x != y) {
			arr[x] = y;
		}
	}
	
	static int find(int x) {
		if (x == arr[x])
			return x;
		else
			return arr[x] = find(arr[x]);
	}
}

태클 감사합니다.
조언 환영입니다.