백준 1717 집합의 표현 - 유니온 파인드

문제 링크

유니온 파인드란.

서로 두 다른 원소가 같은 집합에 포함되어 있는지 확인할 수 있는 알고리즘이다.

유니온(합집합), 파인드(찾기) 함수로 이루어져 있다.

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

        parent[x] =find(parent[x]);

        return parent[x] ;
    }

    public static void union(int x, int y){
        if(x > y){
            int tmp = x;
            x = y;
            y = tmp;
        }
        // x 가 작음

        int xRoot = find(x);
        int yRoot = find(y);

        if(xRoot == yRoot){
            return ;
        }

        parent[yRoot] = xRoot;
    }

놓친점 1

유니온 파인드를 개념적으로 이해하긴 쉽지만 중간에 놓치면 안될 중요한 포인트가있다.
바로 find 함수에서 경로압축에 따라 시간복잡도 차이가 log(n) 과 n으로 큰 차이가 난다는 것이다.

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

        parent[x] =find(parent[x]);

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

		return find(parent[x]);
    }

위 코드는 경로압축, 아래는 그냥 코드이다.
경로 압축을 했을땐 부모에 실제 부모가 아닌 가장 높은 root 부모로 저장하고 리턴하게 된다.
이므로써 중복연산을 줄이고 시간복잡도를 개선할 수 있다.

최종 코드

import java.io.*;
import java.util.*;


public class Main {


    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


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

        parent[x] =find(parent[x]);

        return parent[x] ;
    }

    public static void union(int x, int y){
        if(x > y){
            int tmp = x;
            x = y;
            y = tmp;
        }
        // x 가 작음

        int xRoot = find(x);
        int yRoot = find(y);

        if(xRoot == yRoot){
            return ;
        }

        parent[yRoot] = xRoot;
    }

    public static void main(String[] args) throws IOException {
        String[] inp = br.readLine().split(" ");

        int n = Integer.parseInt(inp[0]);
        int m = Integer.parseInt(inp[1]);

        parent = new int[n+1]; // 1인덱싱

        for(int i=0;i<n;i++){
            parent[i+1]=i+1;
        }

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

            if(cmd==0){
                union(a,b);
            }else{

                if(find(a)==find(b)){
                    bw.write("YES\n");
                }
                else{
                    bw.write("NO\n");
                }
            }
        }

        bw.flush();

    }
}