[BOJ] 4195. 친구 네트워크

이 문제는 유니온파인드를 사용하는 문제이다.

유니온파인드를 사용하고 같은 그룹안에 몇개의 원소가 있는지 구하는 문제이다. 이 문제는 주의할점이 있다. 바로 입력의 형태가 문자열의 형태로 들어오기때문에 HashMap을 이용하여 이름을 인덱싱해주는 작업이 필요하다. 인덱싱을 해준후 count라는 배열을 이용하여 union할때마다 원소를 합쳐주는 과정을 거쳐 최종 결과를 출력해주면 된다.

package boj1;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
 
public class Main_bj_4195_친구네트워크_2 {
    
    
    static Map<String, Integer> map;
    static int[] p;
    static int[] count;
    static int N;
    
    static int cur;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int T=Integer.parseInt(br.readLine());
    
        for(int tc=0;tc<T;tc++) {
            N=Integer.parseInt(br.readLine());
            
            cur=0;
            p=new int[2*N+1];
            count=new int[2*N+1];
            
            for(int i=0;i<2*N+1;i++) {
                p[i]=i;
                count[i]=1;
            }
            map=new HashMap<>();
            for(int i=0;i<N;i++) {
                st=new StringTokenizer(br.readLine());
                int num1=getIndex(st.nextToken());
                int num2=getIndex(st.nextToken());
                
                union(num1, num2);
                
            }
        }
    }
    
    static int getIndex(String str) {
        if(map.containsKey(str)) {
            return map.get(str);
        }
        map.put(str, cur);
        cur=cur+1;
        return map.get(str);
    }
    
    static int find(int num) {
        if(p[num]==num)
            return num;
        return p[num]=find(p[num]);
    }
    
    static void union(int num1,int num2) {
        num1=find(num1);
        num2=find(num2);
        
        if(num1<num2) {
            p[num2]=num1;
            count[num1]+=count[num2];
            System.out.println(count[num1]);
        }
        else if(num1>num2){
            p[num1]=num2;
            count[num2]+=count[num1];
            System.out.println(count[num2]);
        }else {
            System.out.println(count[num1]);
        }
        
    }
}