[BOJ 4195] 친구 네트워크(Java, Union-Find, 간단한 코드)

## 접근

---

• 친구 네트워크가 이룬다는 것은, 몇몇의 친구들이 같은 집단에 속한다는 것을 의미한다. 집단에 관한 처리를 가장 빠르게 할 수 있는 것은, Union-Find이다.
  
  
• 친구들이 입력될 때마다, Union 연산을 통해서 합쳐주고, 인원수를 별도의 자료구조에 저장해서 갱신하도록 한다.
  
  

 

 

 

## 유의사항

---

• 처음에 메모리 초과가 발생했었는데, 이유는 Find 연산 시에, 재귀적으로 계속 호출되서 스택 오버플로우가 발생했다. 항상, 재귀연산을 작성할 때는 무한 반복이 될 수 있는 가능성을 확인하고 코드를 작성해야 한다.

 

 

 

 

## 해설코드

---

import java.util.*;
import java.lang.*;
import java.io.*;
 
public class Main{
    static HashMap<String, String> hm;
    static HashMap<String, Integer> cntHm;
    
    static String find(String x){
        if(x.equals(hm.get(x)) || !hm.containsKey(x)){
            return x;
        }
        else{   
            hm.put(x, find(hm.get(x)));
            return hm.get(x);
        }
    }
    
    static void union(String x, String y){
        String rootX = find(x);
        String rootY = find(y);
        
        int cntX = cntHm.getOrDefault(rootX, 1);
        int cntY = cntHm.getOrDefault(rootY, 1);
        
        if(!rootX.equals(rootY)){
            cntHm.put(rootX, cntX + cntY);
            cntHm.put(rootY, cntX + cntY);
        }else
            cntHm.put(rootX, cntX);
        
        hm.put(rootX, rootY);
    }
 
     public static void main (String []args) throws java.lang.Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));    
    
        int T = Integer.valueOf(br.readLine());
        String[] sArr;
        String s1, s2;
        
        hm = new HashMap<>();
        cntHm = new HashMap<>();
         
        for(int i = 1; i <= T; i++){
            int N = Integer.valueOf(br.readLine());
            hm.clear();
            cntHm.clear();
            
            for(int j = 1; j <= N; j++){
                sArr = br.readLine().split(" ");
                s1 = sArr[0];
                s2 = sArr[1];
                
                union(s1, s2);
                bw.write(cntHm.get(find(s1)) + "\n");
            }
        }
        
        
        bw.flush();
     }
}