[BOJ 1717] 집합의 표현(Java)

---

문제

집합의 표현

---

문제 해설

전형적인 Union-Find 문제이다. 단, 주의할 점은 Union-Find로 구현할 때 반드시 경로 압축을 해야만 시간초과에 걸리지 않는다.

경로 압축?

• 일반적인 방법으로는 다음과 같이 구현한다.

static int find(int x) {
		if (parents[x] == x) {
			return x;
		}
		return find(parents[x]);
	}

하나의 노드를 기준으로 부모를 따라 계속 탐색하는 방식이다.
이 방법은 치명적인 단점이 존재하는데, 노드의 크기가 커질수록 트리의 높이가 깊어져 O(n)이라는 오랜 시간이 걸리게 된다. 문제의 N과 M은 각 1,000,000, 100,000 이므로 시간초과가 난다.

사진 출처
그렇기 때문에 부모를 찾을때마다 해당 집합에 연관되어 있는 노드들의 부모를 전부 최상위 부모로 바꿔주는 작업이 필요한데, find를 할때 return 값으로 최상위 부모를 모든 노드에 연결하는 방식을 사용한다.

static int find(int x) {
		if (parents[x] == x) {
			return x;
		}
		// 경로 압축
		return parents[x] = find(parents[x]);
	}

이런 방식을 사용하면 트리의 높이가 짧아지며, 같은 집합 내의 노드들은 바로 최상위 노드로 연결 된다. 시간복잡도는 O(logn)이다.

사진 출처

주의점

단, 주의할 점이 있는데 경로압축을 하더라도 같은 그룹의 하위 노드들은 부모가 바뀌지 않는다는 점이다. 따라서, 모든 노드의 부모노드를 묻는 문제라면 각 노드마다 find()를 한번 거쳐야 정확한 답을 얻을 수 있을 것이다.

---

풀이 코드

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

public class BOJ1717_집합의표현 {
	// 4:44 ~ 5:02
	static int n, m;
	static int[] parents;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		parents = new int[n + 1];
		for (int i = 0; i < n + 1; i++) {
			parents[i] = i;
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.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 {
				System.out.println(find(a) != find(b) ? "NO" : "YES");
			}
		}
	}

	static void union(int x, int y) {
		x = find(x);
		y = find(y);
		// 작은 수로 합치기
		if (x < y) {
			parents[y] = x;
		} else {
			parents[x] = y;
		}
	}

	static int find(int x) {
		if (parents[x] == x) {
			return x;
		}
		// 경로 압축
		return parents[x] = find(parents[x]);
	}

}

---