[알고리즘] 서로소 집합

서로소

서로소 집합

서로 중복된 원소가 없는 집합을 의미 == 교집합이 없는 집합

집합에 속한 특정 멤버(대표자)를 통해 집합을 구분

대표자는 어떤 데이터가 되든 상관이 없음

하나의 집합에는 오로지 하나의 대표자만 가질 수 있음

 

 

서로소 집합 연산

1) init : 초기화

2) union : 두 개의 집합을 하나의 집합으로 결합

3) find : 집합 내의 대표자를 찾음

 

 

서로소의 최적화

- Rank 사용

기본 서로소 함수에서는 부모를 찾을 때 find의 재귀가 여러 번 발생함

-> 두 서로소를 결합할 때 더 낮은 트리를 더 높은 트리의 자식으로 결합하면 효율성을 높일 수 있음

(데이터에 따라서 사용하지 않을 때 더 빠른 경우가 있음)

 

 

- Path 사용

find함수의 재귀가 발생하여 부모의 결과를 찾으면, 해당 결과를 변수에 저장함으로써 부모를 찾기 위한 재귀가 적게 일어나도록 유도

 

 

 

코드

서로소는 일반적으로 배열과 리스트를 사용하여 만들 수 있으며,

배열을 통해 구현하는 경우 배열의 인덱스가 노드의 위치를, 배열의 데이터가 연결된 부모 노드를 나타냄

public class Main {
	static int N = 8;
	static int[] rank = new int[N]; // Rank(높이값) 저장 배열
	static int[] parents;

	public static void main(String[] args) {
		parents = new int[N]; // 각 노드별 대표자 노드 연결 번호를 저장

		// 1) make set
		for (int i = 0; i < parents.length; i++) {
			parents[i] = i;
		}

		// 2) union
		union(0, 2); union(1, 2); union(3, 4); union(6, 4);
		union(7, 4); union(4, 5); union(3, 1);

	}

	private static void union(int a, int b) {
		// 3) find
		int pa = find(a);
		int pb = find(b);

		// 두 조직의 대표가 다르면 다른 조직이므로 합침
		if (pa != pb) {
			// 일반 코드
			// parents[pa] = pb;

			// rank code
			// b조직이 a조직보다 높이가 높다면 a조직이 b조직 밑으로 들어간다.
			if (rank[pb] > rank[pa]) {
				parents[pa] = parents[pb];
			} else {
				parents[b] = parents[a];
				if (rank[a] == rank[b]) {
					rank[b]++;
				}
			}
		}
	}

	private static int find(int a) {
		if (parents[a] == a) {
			return a;
		} else {
			// 일반적인 방식
			// return find(parents[a]); // 재귀를 통해 대표자 찾기

			// path compression
			return parents[a] = find(parents[a]); // 재귀를 통해 대표자 찾기
		}
	}
}

 

// 백준(1717) 집합의 표현

public class 집합의표현 {

	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());
		StringBuilder sb = new StringBuilder();

		ArrayList<ArrayList<Integer>> node = new ArrayList<>();

		// 첫 번째 줄
		int n = Integer.parseInt(st.nextToken()); // 최대 값
		int m = Integer.parseInt(st.nextToken()); // 연산 횟수

		// 부모 값 저장
		parents = new int[n + 1];

		// 초기값 지정
		for (int i = 0; i < parents.length; i++) {
			parents[i] = i;
		}

		// 나머지 줄
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int action = Integer.parseInt(st.nextToken()); // 0 = 합치기, 1 = 합쳐졌는지 확인
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			if (action == 0) {
				union(a, b);
			} else {
				int pa = find(a);
				int pb = find(b);

				// 부모가 같으면
				if (pa == pb) {
					sb.append("YES\n");
				} else {
					sb.append("NO\n");
				}
			}
		}
		System.out.println(sb);
	}

	// 합집합
	private static void union(int a, int b) {
		int pa = find(a);
		int pb = find(b);

		// 왼쪽 집합을 오른쪽에 합침
		parents[pa] = pb;

	}

	// 부모 찾기
	private static int find(int a) {
		if (parents[a] == a) {
			return a;
		} else {
			return parents[a] = find(parents[a]);
		}
	}

}

 

 

 

대표 문제

- 정올 종교 (기본 개념 + 무리 개수 찾기)

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1136&sca=99&sfl=wr_hit&stx=1863 

 

- SWEA 창용마을무리의개수 (기본 개념 + 무리 개수 찾기)

https://angelplayer.tistory.com/427

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU&categoryId=AWngfZVa9XwDFAQU&categoryType=CODE&problemTitle=7465&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

 

- SWEA 서로소집합 (기본 개념)

https://angelplayer.tistory.com/428

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJKA6qr2oDFAWr 

 

- 백준 공항 (응용)

https://angelplayer.tistory.com/430

https://www.acmicpc.net/problem/10775