[BOJ] 1717. 집합의 표현

문제

BOJ 1717. 집합의 표현

Disjoint-set (서로소 집합)

• 서로 중복 포함된 원소가 없는 집합들. 즉, 교집합이 없다.
• 집합에 속한 하나의 특정 멤버(대표자)를 통해 각 집합들을 구분

서로소 집합 연산

• Make-Set(x)
• Find-Set(x)
• Union(x,y)

풀이

union-find 알고리즘을 사용해서 푸는 문제로 0이 입력됐을 땐 union(a,b)를 호출하여 a와 b의 부모 중에서 더 작은 쪽으로 union해주었다. 그리고 1이 입력됐을 땐 find(a)를 호출하고 a의 부모가 자기 자신이 아니라면 find(parent[a])를 재귀적으로 호출하고 parent[a]에 대입함으로써 경로압축(Path Compression)을 적용해주었다.

JAVA코드

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

public class 백준1717_집합의표현 {

	static int[] parent; // 부모
	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());

		parent = new int[N + 1];

		make();
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int type = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			if (type == 0) { // union
				union(a, b);
			} else if (type == 1) { // find
				int findA = find(a);
				int findB = find(b);
				if (findA == findB)
					sb.append("YES\n");
				else
					sb.append("NO\n");
			}

		}

		System.out.println(sb.toString());
	}

	// 합
	static public void union(int a, int b) {
		int parentA = find(a);
		int parentB = find(b);

		if (parentA != parentB) { // 부모가 서로 다르다면
			if (parentA > parentB) // 더 작은 쪽의 부모로 union
				parent[parentA] = parentB;
			else if (parentA < parentB)
				parent[parentB] = parentA;
		}
	}

	// 초기화 함수
	static public void make() {
		for (int i = 0; i < parent.length; i++) {
			parent[i] = i;
		}
	}

	// 부모 찾기
	static public int find(int num) {
		if (parent[num] == num)
			return num;
		else
			return parent[num] = find(parent[num]); //경로압축
	}
}