[JAVA] 백준 1707 유니온 파인드

 

 

 

 

1717번: 집합의 표현

문제

집합 0~N+1이 주어졌을 때 합집합 연산과 같은 집합에 속하는지 여부를 체크하여 출력하시오.

풀이

유니온 파인드를 물어보는 문제였다.

📌 입출력

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine(), " ");

            boolean c = st.nextToken().equals("0") ? true : false;
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if(c){
                union(a, b);
            }else{
                int x = find(a);
                int y = find(b);
                sb.append(x == y ? "YES" : "NO").append("\n");
            }
        }
        System.out.println(sb);

c : 첫 번째로 오는 수가 0이면 합집합 연산, 1이면 주어진 두 수가 같은 집합에 속하는지 여부를 출력한다.

📌 유니온 파인드

    static void union(int a, int b){
        int x = find(a);
        int y = find(b);

        A[y] = x;
    }

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

    }

union : 두 수의 집합을 찾고 b집합을 a집합에 포함시킨다.

find : 주어진 수의 집합을 찾는다. 재귀적으로 찾으면서 가장 상단의 수를 찾아서 넣는다.

📌 전체 코드

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

class Main {
    static int[] A;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken())+1;
        int M = Integer.parseInt(st.nextToken());

        A = new int[N];
        for(int i=0; i<N; i++){
            A[i] = i;
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine(), " ");

            boolean c = st.nextToken().equals("0") ? true : false;
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if(c){
                union(a, b);
            }else{
                int x = find(a);
                int y = find(b);
                sb.append(x == y ? "YES" : "NO").append("\n");
            }
        }
        System.out.println(sb);

    }

    static void union(int a, int b){
        int x = find(a);
        int y = find(b);

        A[y] = x;
    }

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

    }

}

결과