[백준] 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이며 같을 수도 있다.

 

출력

 

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

 

 

풀이 방법

 

두 개의 원소가 같은 집단인지 확인하는 문제로 union-find 알고리즘을 이용하여 문제를 풀이하였다.

처음에 parent[] 배열을 통해 자신의 인덱스값으로 초기화를 시켜준 뒤, 연결이 되어있다면 작은 원소로 배열을 초기화 시켜주면 된다.

이후, find 메서드에서 부모의 최상층 인덱스를 따라가는 로직을 작성해주고 union 메서드에서는 작은 원소의 값으로 초기화 해주는 과정을 거치면 된다.

 

작성 코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

import java.util.*; import java.io.*;   public class Main {       static int n,m;     static int parent[];       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());           n = Integer.parseInt(st.nextToken());         m = Integer.parseInt(st.nextToken());           parent=new int[n+1];         for(int i=1;i<=n;i++){             parent[i]=i;         }           for(int i=0;i<m;i++){             st=new StringTokenizer(br.readLine());             int num=Integer.parseInt(st.nextToken());             int a=Integer.parseInt(st.nextToken());             int b=Integer.parseInt(st.nextToken());             if(num==0){                 union(a,b);             }             else {                 if(find(a)==find(b)){                     System.out.println("YES");                 } else {                     System.out.println("NO");                 }             }         }     }       public static int find(int child){         if(parent[child]==child){             return child;         }         return parent[child]=find(parent[child]);     }       public 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;         }     } }