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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

/*
 * [조건]
 * 시간제한 : 3초 / 메모리제한 : 256MB
 * F <= 100,000 / name.length() <= 20
 * [풀이]
 * Union find 알고리즘을 통해 공통 친구 네트워크의 개수를 구한다.
 * 친구 집합의 root를 find를 통해 찾는다.
 * root가 아직 정해지지 않았다면, 공통 집합에 가입시킨다.
 * 두 친구관계가 만나면 Union을 통해 공통 집합에 가입시키고, 공통 집합의 크기를 더한다.
 */
public class bj_4195_친구_네트워크 {

    static int groupId = 0;
    static HashMap<String, String> friendship; // 친구관계(부모)를 가리키는 해시맵
    static HashMap<String, Integer> rootCount; // 네트워크 크기를 루트와 매핑하는 해시맵

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            int F = Integer.parseInt(br.readLine());
            friendship = new HashMap<>();
            rootCount = new HashMap<>();
            for (int j = 0; j < F; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                String f1 = st.nextToken();
                String f2 = st.nextToken();
                System.out.println(getFriends(f1, f2));
            }
        }
    }

    /*
     * 집합(친구관계)을 생성하는 메서드
     */
    static void makeSet(String s) {
        friendship.put(s, s);

        // 최초 친구 : 1명
        rootCount.put(s, 1);
    }

    /*
     * 각 네트워크의 루트를 찾아(Find) 두 관계를 합치는 메서드
     * 왼쪽값의 root에 오른쪽을 편입시킴
     */
    static int union(String s1, String s2) {
        String root1 = find(s1);
        String root2 = find(s2);

        // 이미 친구일 경우 예외처리
        if (root1.equals(root2)) return rootCount.get(root1);

        // 네트워크 편입
        friendship.put(root2, root1);

        // 편입 시 두 네트워크의 합으로 루트 해시맵의 값을 변경, 네트워크의 합 return
        int value = rootCount.get(root1) + rootCount.get(root2);
        rootCount.put(root1, value);
        return value;
    }

    /*
     * 부모를 찾는 메서드
     * HashMap의 값이 본인이 아니면 본인이 나올때까지 재귀호출하여 path compression
     * HashMap의 값 == 본인 이면 root
     */
    static String find(String me) {

       // Recursive Path Compression(재귀적으로 부모값을 루트로 변경시켜 이후 탐색속도 높임)
        if (!me.equals(friendship.get(me)))
          friendship.put(me, find(friendship.get(me)));

        return friendship.get(me);
    }

    /*
     * 두 네트워크를 합치고 공통의 친구 개수를 찾는 메서드
     */
    static int getFriends(String f1, String f2) {
        if (!friendship.containsKey(f1)) makeSet(f1);
        if (!friendship.containsKey(f2)) makeSet(f2);
        return union(f1, f2);
    }
}