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

1.  문제 링크

https://www.acmicpc.net/problem/4195

2.  문제

요약

• 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말합니다.
• 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 문제입니다.
• 입력: 첫 번째 줄에 테스트 케이스의 개수가 주어집니다. 각 테스트 케이스의 첫 번째 줄에 100,000보다 작거나 같은 친구 관계의 수 F가 주어지고 두 번째 줄부터 F개의 줄에 친구 관계가 생긴 순서대로 주어집니다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열입니다.
• 출력: 친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static Reader scanner = new Reader();
    static int F;
    static HashMap<String, Integer> people;
    static int[] parents, children;
    static void input() {
        F = scanner.nextInt();
        people = new HashMap<>();
        parents = new int[F * 2];
        children = new int[F * 2];
        int idx = 0;
        for(int relation = 0; relation < F; relation++) {
            String person1 = scanner.next(), person2 = scanner.next();
            if(!people.containsKey(person1))
                idx = addPerson(idx, person1);
            if(!people.containsKey(person2))
                idx = addPerson(idx, person2);

            sb.append(union(people.get(person1), people.get(person2))).append('\n');
        }
    }

    static int addPerson(int idx, String person) {
        people.put(person, idx++);
        parents[people.get(person)] = people.get(person);
        children[people.get(person)]++;
        return idx;
    }

    static int findParent(int person) {
        if(person == parents[person]) return person;
        return parents[person] = findParent(parents[person]);
    }

    static int union(int person1, int person2) {
        int parent1 = findParent(person1), parent2 = findParent(person2);
        int result = children[parent1];

        if(parent1 != parent2) {
            if(parent1 < parent2) {
                parents[parent2] = parent1;
                children[parent1] += children[parent2];
                children[parent2] = 1;
                result = children[parent1];
            }
            else {
                parents[parent1] = parent2;
                children[parent2] += children[parent1];
                children[parent1] = 1;
                result = children[parent2];
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int tc = scanner.nextInt();
        while(tc-- > 0) {
            input();
        }

        System.out.print(sb);
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• F개의 친구 관계가 주어지기 때문에 최대 인원 수는 (2 × F) 명이 됩니다.
• 친구 관계에 주어지는 각 사람을 정수로 나타내기 위해 HashMap people을 생성하고 들어온 순서대로 번호를 매겨 people에 저장합니다.
• 각 사람의 부모를 나타내는 배열 people과 각 사람의 자식의 인원 수를 나타내는 배열 children을 생성합니다. 크기는 F개의 친구 관계가 주어지기 때문에 최대 인원 수가 (2 × F) 명이므로 (2 × F)로 크기를 정합니다.
• 친구 관계가 주어질 때마다 Union-Find를 이용하여 각 사람의 부모를 갱신하고, 자식 관계에 해당하는 사람의 자식 인원 수를 부모 관계에 해당하는 사람의 자식 인원 수에 더해줍니다.
  • 두 사람의 친구 네트워크에 몇 명이 있는지 구하려면 친구 관계의 두 사람에 대해 부모-자식 관계를 갱신하는 것 뿐만 아니라, 자식 관계에 있는 사람의 자식들도 모두 두 사람의 친구 네트워크에 포함되기 때문에 부모 관계에 있는 사람의 자식 인원 수에 자식 관계에 있는 사람의 자식 인원 수를 더해줍니다.