[백준 4195] 친구 네트워크(Java)

문제 링크 : https://www.acmicpc.net/problem/4195

이 문제는 유니온 파인드를 이용하여 풀 수 있습니다. 이 문제의 가장 어려운 부분은 문자열을 유니온 파인드로 그룹화하기입니다. 이를 위해 맵을 이용하여 각 문자열을 키로, 유니온 파인드를 수행할 배열의 인덱스를 벨류로 할당하는 방식으로 진행합니다.

여기서 유니온 과정을 진행할 때 다른 그룹의 크기만큼 그룹의 크기가 증가하기 때문에 현재 노드의 크기 정보도 함께 저장해야 합니다. 따라서 병합 시 병합되는 노드의 크기만큼 병합하는 노드에 더해주고 그 크기를 리턴합니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

class Main{
    static int[] parent,level;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        while(T-- >0){
            int F = Integer.parseInt(br.readLine());
            parent = new int[F*2];
            level = new int[F*2];
            for(int i=0;i<F*2;i++){
                parent[i] = i;
                level[i] = 1;
            }

            int idx = 0;
            Map<String,Integer> map = new HashMap<>();
            for(int i=0;i<F;i++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                String first = st.nextToken();
                String second = st.nextToken();

                if(!map.containsKey(first)) map.put(first,idx++);
                if(!map.containsKey(second)) map.put(second,idx++);

                sb.append(union(map.get(first), map.get(second))).append("\n");
            }
        }
        System.out.println(sb);
    }

    static int union(int a, int b){
        a = find(a);
        b = find(b);
        if(a != b){
            parent[b] = a;
            level[a] += level[b];
        }
        return level[a];
    }

    static int find(int a){
        if(a == parent[a]) return a;
        else return parent[a] = find(parent[a]);
    }
}