<Algorithm> 185. 창용마을 무리의 개수(SWExpert)

1. 창용마을 무리의 개수(SWExpert)

   사용 알고리즘 : UnionFind

• UnionFind를 공부했더니 보자마자 UnionFind 문제라는 느낌이 왔다. 이제 좀 감을 확실하게 잡은 것 같다.

 

문제에 대한 접근&생각

1. 친한 사람이 연결 되어있고 무리를 지음, 이 무리의 개수 -> 각각의 루트노드를 가지면 되겠다 -> UnionFind
2. 연결된 모든 사람에 대해 Union -> Set을 이용해 모든 사람의 노드를 저장

내 코드 

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 57 58

import java.util.HashSet; import java.util.Scanner; import java.util.Set;   public class Solution {     static int[] parent,level;     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int test = sc.nextInt();         for(int t = 1; t<=test; t++) {             /***************************              * UnionFind를 이용해 친구의 친구들을              * 모두 연결하여 무리의 개수를 구한다.              ***************************/             int n = sc.nextInt();             int m = sc.nextInt();             parent = new int[n];             level = new int[n];             for(int i = 0; i < n; i++) {                 parent[i] = i;                 level[i] = 1;             }                          for(int i = 0; i < m; i++) {                 union(sc.nextInt()-1, sc.nextInt()-1);             }          Set<Integer> set = new HashSet<>();          for(int i = 0; i < n; i++) {              set.add(find(i));          }                      System.out.println("#"+t+" "+set.size());         }     }          private static int find(int v) {         if(v == parent[v]) return v;         else return parent[v] = find(parent[v]);     }     private static void union(int i,int j) {         int iroot = find(i);         int jroot = find(j);                  if(iroot == jroot) return;                  if(level[iroot]<level[jroot]) {             int temp = iroot;             iroot = jroot;             jroot = temp;         }         parent[jroot] = iroot;                  if(level[iroot] == level[jroot]) {             level[iroot]++;         }     } }  Colored by Color Scripter

cs

 

 

얻은 것

• 갯수는 잘못된 표기고 개수가 표준어라는 것 알았다;;