[유니온 앤 파인드] 백준 1717. 집합의 표현

유니온앤파인드(Union And Find)

그래프/트리에서 쓰는 대표적인 알고리즘으로, 서로소인 부분집합을 표현한다.

즉, 여러 노드가 있을때 두 노드가 같은 그래프에 있는가?를 판단할 수 있는 알고리즘이다.

union(합치는)연산과 find(어느 집합에 속하는지)연산으로 이루어져있다.

 

 

알고리즘 구현 방법

1. parent[] 배열을 만들고, 각 인덱스에 인덱스값을 넣는다(parent[i] = i, 모든 노드가 자기자신을 부모로 가리킨다)

2. union(a,b)의 경우, a와 b를 합치는 작업을 한다. parent[2]=1이 됨으로써 집합을 표현할 수 있다(더 작은값 쪽으로 합친다)

3. 그러나 이렇게했을경우, 1-2-3이 연결되었을때 parent[1]=1, parent[2]=2, parent[3]=2가 되기 때문에 합집합을 알아보기 힘들다. 따라서 union이전에 find과정을 통해서 부모값을 미리 찾아야한다. 따라서 기본적인 코드는 다음과 같다.

static void make() {
    parents = new int[V];
    for(int i=0; i<V; i++) parents[i] = i;
}

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

static boolean union(int a, int b) {
    int aRoot = find(a);
    int bRoot = find(b);
    if(aRoot == bRoot) return false; //싸이클 발생
    parents[bRoot] = aRoot;
    return true;
}

 

 

백준 1717. 집합의 표현

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

 

0이 주어지면 합집합 연산을, 1이 주어지면 두 노드가 같은 집합안에 속하는지 확인하는 연산을 수행한다.

따라서, Union을 통해 0연산을 수행하고, find연산을 통해 1연산을 수행하면 된다.

 

cf)

공간복잡도 : parent배열 크기(n+1) => O(n)

시간복잡도 : make메소드(O(n)) + 유니온앤파인드O(α(n)) => O(m α(n))

 

풀이

1. parent[]함수를 만들어 초기화한다.

2. 모든 명령어를 순회

    2-1. 0일땐 union을 실행

    2-2. 1일땐 find한 후 같은 집합이면 YES, 아니면 NO 누적

 

public class Main {
    static int[] parents;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        parents = new int[n+1];
        for(int i=0; i<n+1; i++) parents[i] = i;

        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            if(a == 0) union(b,c);
            else if(a==1) {
                if(find(b) == find(c)) sb.append("YES").append('\n');
                else sb.append("NO").append('\n');
            }
        }
        System.out.println(sb);
    }

    private static boolean union(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);

        if(aRoot == bRoot) return false;
        parents[bRoot] = aRoot;
        return true;
    }

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