서로소 집합 (Union Find)

서로소 집합 (Disjoint-set)

서로소 집합이란?

공통 원소가 없는 두 집합을 의미한다. 즉, 서로 중복 포함된 원소가 없는 집합이고 교집합이 없다.

• 집합에 속한 하나의 대표자를 통해 각 집합들을 구분

서로소 집합 연산

• Make set(x)
• Find set(x)
• Union(x, y)

서로소를 표현하는 방법

• 연결리스트
• 트리

연결리스트

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

트리

• 같은 집합의 원소들은 하나의 트리로 표현한다.
• 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다.

구현 방법

앞서 말했던 3가지 연산을 차례로 구현해야한다.
1) 초기 - make set으로 모두 각각 독립된 집합으로 분리한다.

static int[] MakeSet(int size) {
	int[] parent = new int[size + 1];
    for (int i = 0; i <= size; i++) {
    	parent[i] = i;
    }
    return parent;
}

2) Find Set(x) : x를 포함하는 집합을 찾는 연산

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

3) Union(x, y) : x, y를 포함하는 두 집합을 합치는 연산

static void union(a, b) {
	int parentA = find(a);
    int parentB = find(b);
    if (parentA == parentB) return;
    parent[b] = parent[a];
}

문제점

계속 find 연산을 실행하는 x가 트리의 리프노드인 경우 -> 많은 연산을 통해 계속 대표자를 찾게 됨.

해결방안

• Rank를 이용
  - 각 노드는 자신을 루트로 하는 subtree의 높이를 rank로 저장한다
  -union 시 rank가 낮은 집합을 rank가 높은 집합에 붙인다.
• Path compression
  - Find 연산을 할 시 만나는 모든 노드들이 직접 root를 가리키도록 포인터를 업데이트 해준다.

Path Compression 적용

Find Set

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

예시 문제 (BOJ1976_여행가자)

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

package blog;

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

public class DisjointSet {
    static int[] parent;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        // Make Set
        parent = new int[N+1];
        for (int i = 1; i <= N; i++) parent[i] = i;

        for (int from = 1; from <= N; from++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int to = 1; to <= N; to++) {
                int link = Integer.parseInt(st.nextToken());
                if (link == 1) {
                    union(from, to);
                }
            }
        }
        int target = 0;
        boolean possible = true;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int city = Integer.parseInt(st.nextToken());
            if (i == 0) target = find(city);
            else {
                int parentCity = find(city);
                if (target != parentCity) {
                    possible = false;
                    break;
                }
            }
        }
        System.out.println(possible ? "YES" : "NO");
        br.close();
    }
    static int find(int x) {
        if (x == parent[x]) return x;
        return parent[x] = find(parent[x]);
    }
    static void union(int x, int y) {
        int parentX = find(x);
        int parentY = find(y);
        if (parentX == parentY) return;
        parent[parentY] = parent[parentX];
    }
}