백준(4195번) - 친구 네트워크

문제 출처: https://www.acmicpc.net/problem/4195

문제

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

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

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

    private static int[] parents, cnt;

    private static void makeSet(int n) {
        parents = new int[n];
        cnt = new int[n];

        for (int i = 0; i < n; i++) {
            parents[i] = i;
            cnt[i] = 1;
        }
    }

    private static boolean unionSet(int a, int b) {
        int parentA = findSet(a);
        int parentB = findSet(b);

        if (parentA == parentB) return false; // 이미 같은 집합

        parents[parentB] = parentA;
        cnt[parentA] += cnt[parentB];

        return true;
    }

    private static int findSet(int a) {
        if (a == parents[a]) return a;

        return parents[a] = findSet(parents[a]); // Path Compression
    }

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(reader.readLine()); // 테스트케이스 개수

        while (T-- > 0) {
            int F = Integer.parseInt(reader.readLine()); // 친구 관계의 수

            Map<String, Integer> map = new HashMap<>();
            int index = 0;

            makeSet(F * 2);

            for (int i = 0; i < F; i++) {
                StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
                String a = tokenizer.nextToken();
                String b = tokenizer.nextToken();

                if (!map.containsKey(a)) map.put(a, index++);
                if (!map.containsKey(b)) map.put(b, index++);

                unionSet(map.get(a), map.get(b));

                sb.append(cnt[parents[map.get(a)]]).append("\n");
            }
        }

        System.out.println(sb);
    }

}

• Union-Find 알고리즘에서 약간 추가한 방법으로 풀 수 있는 문제였다.
• 처음 문제를 풀 때 문제를 꼼꼼히 읽지 않아 ArrayIndexOutOfBounds 예외가 떴다.
• 들어오는 'F' 값이 친구의 수가 아니라 친구 관계의 수였는데 이를 친구의 수로 배열의 크기로 넘겨주어 에러가 뜬 것이다.
• 친구의 수를 확정지을 수 없으므로 최대의 수인 친구 관계 수 * 2 만큼으로 잡았다.
• 각 대표자 별 밑에 있는 자식의 수를 기억하는 배열을 따로 둔다.
• Union 연산을 수행할 때 대표자가 바뀌는데, 바뀌기 전 자신의 밑에 있던 수를 새로운 대표자의 수에 더해주어 값을 업데이트해준다.