문제

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

출력

친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

예제 입력 1

2
3
Fred Barney
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty

예제 출력 1

2
3
4
2
2
4

문제 접근

1. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 문제

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    private static HashMap<String, String> hm;
    private static HashMap<String, Integer> size;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());

        while (t-- > 0) {
            int f = Integer.parseInt(br.readLine());
            hm = new HashMap<>();
            size = new HashMap<>();

            for (int i = 0; i < f; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                String friend1 = st.nextToken();
                String friend2 = st.nextToken();

                hm.put(friend1, hm.getOrDefault(friend1, friend1));
                size.put(friend1, size.getOrDefault(friend1, 1));

                hm.put(friend2, hm.getOrDefault(friend2, friend2));
                size.put(friend2, size.getOrDefault(friend2, 1));

                bw.write(union(friend1, friend2) + "\\n");
            }
        }
        bw.flush();
        br.close();
        bw.close();
    }

    private static int union(String friend1, String friend2) {
        friend1 = find(friend1);
        friend2 = find(friend2);

        if (!friend1.equals(friend2)) {
            hm.put(friend2, friend1);
            size.put(friend1, size.get(friend1) + size.get(friend2));
        }
        return size.get(friend1);
    }

    private static String find(String friend) {
        if (friend.equals(hm.get(friend))) return friend;
        hm.put(friend, find(hm.get(friend)));
        return hm.get(friend);
    }
}

참고 링크

1. Union-By-Size 연산 사용