코딩테스트

[알고리즘] Union Find, 서로소 집합, 상호 배타 집합

행복한 토마토 2024. 9. 24. 02:21

Union Find란?

여러 개의 서로소 집합을 병합하고 서로 다른 원소들이 같은 집합에 속해있는지 아닌지를 판별하는데 사용하기 위한 알고리즘이다.  크게 makeSet(),Union(), Find() 세가지의 연산으로 이루어진다.

Union : 병합, 합집합을 의미한다.

Find : 원소가 어떤 집합에 속해 있는지 탐색한다.


서로소 집합 (상호 배타 집합)이란?

공통 원소가 공집합 뿐, 공통 원소가 없는 두 집합을 의미하는데, 공약수가 1뿐인 두 정수를 의미하는 서로소의 개념이 집합으로 확장된 것이다. 직 교집합이 존재하지 않고, 각 집합은 대표자를 통해 구분한다.

 


표현 방법

이러한 서로소 집합을 나타내는 방식에는 크게 두가지가 있다.

 

1. 연결 리스트

  • 같은 집합의 원소들을 하나의 연결 리스트로 관리한다.
  • 연결 리스트의 맨 앞 원소를 집합의 대표자로 결정한다.
  • 각 원소는 집합의 대표 원소를 가리키는 링크를 갖는다.

 

Union(a,b) 결과, a를 대표자로 b가 병합되었다.

 

 

2. 트리

  • 하나의 집합을 하나의 트리로 표현한다.
  • 자식 노드가 부모 노드를 가리키며, 루트 노드가 대표자가 된다.

 

Union(a,b) 결과, a를 대표자로 b가 병합되었다.

 


예시 코드

1. makeSet()

	p = new int[V];
		r = new int[V];
		for (int i = 0; i < V; i++) {
			p[i] = i; // 정점의 대표는 우선 각 정점
			r[i] = 1; // 정점의 랭크(예. 인구수 기준)
		}

 

아래의 그림과 같은 배열을 만든다.

 

2. find()

	private static int find(int v) {
		if (v != p[v]) {
			return p[v] = find(p[v]);
		} else {
			return p[v];
		}
	}

 

각 원소들이 현재 가리키고 있는 부모가 누구인지 확인한다.

 

이때 원소2의 부모는 1, 원소 5의 부모는 3인 것을 알 수 있다.

 

3. Union(a,b)

	private static boolean union(int a, int b) {
		// start의 대표와 end의 대표가 다르면 true;
		a = find(a);
		b = find(b);
		if (a == b) return false; // 사이클이 있다는 뜻
		
		// 대표찾기 : 다르면? 합칠 수 있다
			if (r[a] > r[b]) {
				r[a] += r[b]; // a에 인구수 몰아주자!
				p[b] = a; // b의 대표는 a야!
			} else {
				r[b] += r[a];
				p[a] = b;
			}
			return true;
		
	}

 

각 원소들의 대표를 찾은 뒤, 같은 부모를 갖고 있다면 false를 리턴한다.

만약 부모가 다르다면 rank가 더 높은 원소를 기준으로 병합한다.

 

만약 1과 3이 병합된다면, 1의 rank가 더 높으므로 1이 부모가 되고 3이 자식노드가 될 것이다.


예제

집합의 표현 (백준 1717번, 골드 5)

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

 

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class 집합의표현 {
    static int[] parent;
 
    public static void main(String[] args) throws NumberFormatException, 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];
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }
 
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int order = Integer.parseInt(st.nextToken()); //합쳐라 or 같은집합인지 확인해라
            int a = Integer.parseInt(st.nextToken()); //a가 있는 집합
            int b = Integer.parseInt(st.nextToken()); //b가 있는 집합
 
            if (order == 0) {
                union(a, b);
            } else if (order == 1) {
                sb.append((isSameParent(a, b) ? "YES" : "NO") + "\n");
            } else {
                continue;
            }
        }
 
        System.out.println(sb.toString());
        br.close();
    }
 
    // x의 부모를 찾는 연산
    public static int find(int x) {
        if (x == parent[x]) {
            return x;
        }
 
        return parent[x] = find(parent[x]);
    }
 
    // y의 부모를 x의 부모로 치환하는 연산 (x > y 일 경우, 반대)
    public static void union(int x, int y) {
        x = find(x);
        y = find(y);
 
        if (x != y) {
            if (x < y) {
                parent[y] = x;
            } else {
                parent[x] = y;
            }
        }
    }
 
    // x와 y의 부모가 같은지 확인
    public static boolean isSameParent(int x, int y) {
        x = find(x);
        y = find(y);
 
        if (x == y) {
            return true;
        }
 
        return false;
    }
 
}