[1717번] 집합 표현하기 ( 유니온 파인드 )

---

합집합 연산 -> union 연산
두 원소가 같은 집합에 포함되어 있는지 확인하는 연산 -> find 연산 ( 대표 노드 찾기 )
입력이 크니까 경로 압축이 필요한 전형적인 유니온 파인드 문제이다.

---

✅ 유니온 파인드

find 연산 수행 시 재귀 함수에서 나오면서 탐색한 모든 대표 노드 값을 이번 연산에서 발견한 대표 노드로 변경해주자! ( 경로 압축 )
union 연산 수행 시 선택된 노드끼리 연결하는 것이 아닌 선택된 노드와 대표 노드끼리 연결하는 것에도 주의하자!

[ 구현할 것들 ]
1. 배열 값 초기화
2-1. union실행 (안에 find함수가 들어있음 )
2-2. find 실행

손으로 따라가보자

---

✅ 문제

어려운 문제일수록, 개념을 탄탄히 다져야 변형 문제에도 접근이 가능하다.
습관부터 들이자.

---

✅ 코드

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

public class Main {

	static int[] arr;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int qNum = Integer.parseInt(st.nextToken());

		arr = new int[n + 1];

		for (int i = 0; i < arr.length; i++) {
			arr[i] = i;
		}

		for (int i = 0; i < qNum; i++) {
			st = new StringTokenizer(br.readLine());
			int q = Integer.parseInt(st.nextToken());
			int nodeA = Integer.parseInt(st.nextToken());
			int nodeB = Integer.parseInt(st.nextToken());

			//바로 연결하지 않고 대표노드를 찾아서 연결
			if (q == 0) {
				union(nodeA, nodeB);
			} else if (q == 1) {
				if (find(nodeA) == find(nodeB)) {
					System.out.println("YES");
				} else {
					System.out.println("NO");
				}
			}

		}

	}

	private static void union(int nodeA, int nodeB) {
		//find 연산을 받는다.
		nodeA = find(nodeA);
		nodeB = find(nodeB);

		if (nodeA != nodeB) {
			if (nodeA < nodeB) arr[nodeB] = nodeA;
			else {
				arr[nodeA] = nodeB;
			}
		}

	}

	private static int find(int node) {
		if (arr[node] == node) { //대표 노드면 그 값 return
			return node;
		} else { //데표 노드가 아니면
			//return find(arr[node]); 이렇게만 하면 값을 저장하진 않는다.
			return arr[node] = find(arr[node]); //이렇게 안하면 시간초과 발생
		}
	}
}

---