백준 - 집합의 표현

분리 집합 (Disjoin - Set)

분리 집합(Disjoint Set)이란 교집합이 존재하지 않는 둘 이상의 집합을 말한다.

분리 집합은 교집합을 허락하지 않기 때문에 서로 구분되어야 하는 데이터 집합을 다룰 때 유용하게 쓰인다.

분리 집합을 만들었으면 연산을 해야 한다. 분리 집합의 연산에는 두 가지가 있다.
바로 합집합(Union)과 집합 탐색(Find) 연산이다.

합집합 연산은 분리 집합의 포함 관계를 적절히 활용하면 쉽게 구현할 수 있다.
어떤 원소 노드가 속해 있는 트리의 최상단 노드, 즉 트리의 루트 노드가 곧 원소가 속해 있는 집합이므로 A와 B의 합집합 연산을 수행하고 싶다면 집합 A(또는B)의 부모를 집합 B(또는A)로 위 트리를 예로 들면 1(또는5) 노드의 부모를 5(또는1) 노드로 설정해 주면 되는 것이다. 그럼 아래와 같은 형태가 될 것이다.

출처: https://m.blog.naver.com/PostView.nhn?blogId=wnsgh224&logNo=120196308434&proxyReferer=http:%2F%2F211.193.127.39%2F

유니언 파인드 알고리즘이란?

그래프 알고리즘의 일종으로서 상호 배타적 집합, Disjoint-set 이라고도 합니다. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘입니다. 그러기 위해 두 가지 연산이 존재합니다.

1. Find
   노드 x 가 어느 집합에 포함되어 있는지 찾는 연산
2. Union
   노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산

내 풀이

import sys, copy
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
output = sys.stdin.write

n, m = map(int, input().split())

# n 개의 집합
zip = [i for i in range(n+1)]

# 부모 찾기
def getParent(zip, c):
    if zip[c] == c:
        return c
    zip[c] = getParent(zip, zip[c])
    return zip[c]

# 합집합
def unionParent(zip, a, b):
    a = getParent(zip, a)
    b = getParent(zip, b)
    if a < b:
        zip[b] = a
    else:
        zip[a] = b


# 같은 부모인지 확인하기
def findParent(zip, a, b):
    a = getParent(zip, a)
    b = getParent(zip, b)
    if a == b:
        print("YES\n")
    else:
        print("NO\n")

for _ in range(m):
    t, a, b = map(int, input().split())
    if t == 0:
        unionParent(zip, a, b)
    else:
        findParent(zip, a, b)

자바 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class baekjoon_1717 {

    static int n, m;
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        n = Integer.parseInt(inputs[0]);
        m = Integer.parseInt(inputs[1]);
        parent = new int[n+1];

        for (int i = 0; i < n+1; i++) { //처음에는 자기 자신을 가리킨다.
            parent[i] = i;
        }

        for (int i = 0; i < m; i++) {
            inputs = br.readLine().split(" ");
            int command = Integer.parseInt(inputs[0]);
            int a = Integer.parseInt(inputs[1]);
            int b = Integer.parseInt(inputs[2]);

            if (command == 0) { //합집합 연산
                union(a, b);
            } else if (command == 1) { //확인 연산
                if (find(a) == find(b)) {
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            }
        }
    }

    private static void union(int a, int b) {
        a = find(a);    //부모를 찾는다
        b = find(b);

        if (a == b) { //이미 같은 집합 소속이라면
            return;
        }
        parent[b] = a;
    }

    private static int find(int a) {
        if (parent[a] == a) {
            return a;
        }
        parent[a] = find(parent[a]);
        return parent[a];
    }
}