Do it! 알고리즘 코딩 테스트 (50번)

50번 집합의 표현

---

내가 떠올린 풀이 해설

최대 원소의 개수 1,000,000과 질의 개수 100,000이 큰 편이므로 경로 압축이 필요한 Union Find를 이용해서 푸는 문제이다. 처음에 노드가 연결돼있지 않으므로 대표 노드를 인덱스 값으로 초기화한다. find 연산으로 특정 노드의 대표 노드를 찾고, union 연산으로 2개 노드를 이용해 각 대표 노드를 찾아 연결한다. check 메서드로 a와 b가 같은 집합의 원소인지 확인해 boolean타입으로 리턴해 true면 YES false면 NO를 출력한다.

---

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1717 {
	static int[] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		arr = new int[n + 1];
		for(int i = 0; i <= n; i++) { // 대표 노드를 자기 자신으로 초기화하기 
			arr[i] = i;
		}
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int o = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			if(o == 0) {      // 집합 합치기 
				union(a, b);
			}
			else {  // 같은 집합의 원소인지 확인하기 
				if(check(a, b)) {
					System.out.println("YES");
				}
				else {
					System.out.println("NO");
				}
			}
		}
	}
	private static void union(int a, int b) {  // union 연산: 대표 노드끼리 연결하기 
		a = find(a);
		b = find(b);
		if(a != b) {
			arr[b] = a;
		}		
	}
	private static boolean check(int a, int b) { // 두 원소가 같은 집합인지 확인하기 
		a = find(a);
		b = find(b);
		if(a == b) {
			return true;
		}else {
			return false;
		}
	}
	private static int find(int a) { // find 연산 
		if(a == arr[a]) {
			return a;
		}
		else {
			return arr[a] = find(arr[a]);    // 재귀 함수 형태로 구현 -> 경로 압축 부분
		}
		
	}
}

---

오늘의 회고

Union Find의 알고리즘을 처음 학습하고 오늘은 Union Find를 이용해서 푸는 문제를 풀었습니다. Union Find에서 가장 실수 하는 부분이 find연산을 수행할 때 재귀 함수에서 나오면서 탐색한 모든 노드의 대표 노드 값을 이번 연산에서 발견한 대표 노드로 변경하는 부분과 union연산에서 선택된 노드끼리 연결하는 것이 아닌 선택된 노드의 대표 노드끼리 연결하는 부분이 유니온 파인드에서 가장 많이 실수하는 부분이라고 합니다. 이 부분에서 주의하고 까먹지 않게 철저한 복습과 이해를 하자. 오늘도 복습을 진행하여서 책에 있는 1문제를 풀고 Do it! 알고리즘 코딩 테스트 (29번 ~ 31번) 까지 복습하였습니다.