🎲문제

---

주소 : 백준 1717

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

⌨ 입력

---

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

✅ 풀이

---

풀이방법

전형적인 유니온파인드 문제이다. 합집합을 구성할 때에는 union을 사용하여 부모 자식 관계를 형성하고, 같은 집합인지 확인할 때에는 isSameParent함수로 각각 숫자의 최초 조상이 같은지를 파악하여 같다면 같은 집합이고 아니라면 다른집합이다. 입출력 케이스가 많으므로 buffer를 활용해야 한다.

1. 기본적인 유니온 파인드 알고리즘 을 활용했으므로 유니온파인드를 그대로 가져다 사용하면 된다. N과 M을 입력받고 각각의 부모를 자기 자신으로 초기화 한다.
2. 명령어와 숫자 A, B를 입력받고 명령이 0일 경우 UNION 연산 수행 1일경우 조상이 같은지 확인하는 isSameParent를 사용하여 “YES” “NO”를 출력한다.

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(reader.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for(int i = 1; i <= N; i++)
            parent[i] = i;

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(reader.readLine());
            int command = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if(command == 0)
                union(a,b);
            else
                writer.write(isSameParent(a, b) ? "YES\n" : "NO\n");

        }
        writer.flush();
        writer.close();

    }

1. find는 최초 조상의 부모가 자기 자신을 가르킬 것이므로 재귀를 활용하여 자기 자신을 가르킬때 까지 부모를 찾아나간다.

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

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

1. union은 x와 y를 입력받아 각자의 조상을 찾는다. 각자의 조상이 같을 경우는 이미 통합되어있는 경우이므로 통합할 필요가 없으며, 통합되어있지 않은 경우, 조상이 숫자 크기가 더 작을 경우 해당 조상이 큰 숫자를 조상으로 설정한다.

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

        if(x != y)
            if(x > y)
                parent[y] = x;
            else
                parent[x] = y;
    }

1. isSameParent는 union함수와 같이 각자의 조상을 찾지만 조상이 같거나 다른경우만 판단하여 true나 false를 반환한다.

static boolean isSameParent(int x, int y){
    x = find(x);
    y = find(y);

    if(x == y)
        return true;
    else
        return false;
}

전체 코드

---

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

public class Main{

    static Scanner sc = new Scanner(System.in);
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M;
    static int[] parent = new int[1000001];
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(reader.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for(int i = 1; i <= N; i++)
            parent[i] = i;

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(reader.readLine());
            int command = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if(command == 0)
                union(a,b);
            else
                writer.write(isSameParent(a, b) ? "YES\n" : "NO\n");

        }
        writer.flush();
        writer.close();

    }

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

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

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

        if(x != y)
            if(x > y)
                parent[y] = x;
            else
                parent[x] = y;
    }

    static boolean isSameParent(int x, int y){
        x = find(x);
        y = find(y);

        if(x == y)
            return true;
        else
            return false;
    }

}