[BOJ] 1717 집합의 표현 - JAVA

1. 문제

1717번: 집합의 표현

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

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

---

2. 풀이

메인

static int[] sets;
static int N,M;
public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   StringBuilder sb = new StringBuilder();
   StringTokenizer st = new StringTokenizer(in.readLine());
   N = Integer.parseInt(st.nextToken());
   M = Integer.parseInt(st.nextToken());

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

   for(int i=0;i<M;i++){
      st = new StringTokenizer(in.readLine());
      switch(st.nextToken().charAt(0)){
         case '0':
            union(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
            break;
         case '1':
            if(find(Integer.parseInt(st.nextToken()))==find(Integer.parseInt(st.nextToken()))) sb.append("YES\n");
            else sb.append("NO\n");
            break;
      }
   }

   System.out.print(sb);
}

Union

private static void union(int a, int b) {
   int pa = find(a);
   int pb = find(b);
   if(pa!=pb) sets[pa] = pb;
}

Find

private static int find(int x){
   if(sets[x]==x) return x;
   return sets[x] = find(sets[x]);
}

---

3. 결과

지금까지의 지식으로는 이해할 수 없는 결과가 나왔다. main 밖에 static을 쓰면 전역+정적변수라서 저장위치때문에 지역변수보다 접근시간에서 더 불리하다고 생각했다. 

사진상의 노란색, 파란색끼리 같은 코드인데 n,m을 staic으로 밖에 빼고 안빼고에 따라 시간차이가 저렇게 많이 난다. 

이 부분에서는 왜 그런지 좀 더 공부가 필요할 것 같다.