[BOJ/Union-Find] 백준 4195 - 친구 네트워크 (Java)

4195 - 친구 네트워크

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

문제

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램
(친구 네트워크: 친구 관계만으로 이동할 수 있는 사이)

입력
첫째 줄: 테스트 케이스 개수
각 테스트 케이스 첫째 줄: 친구 관계 수 F (< 100,000)
다음 F개의 줄: 친구 관계 생긴 순서(두 사용자 아이디 <= 20, 문자열)
출력: 친구 관계 생길 때마다 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램

---

풀이

• Union-Find
  • `unf[fb] = fa`: `fb`를 `fa` 밑으로 붙임 = `fa`가 대표
  • `size[fa] += size[fb]`: 두 네트워크 크키 합침
• `Map<String, Integer> HM = new HashMap<>()`: 이름, 고유번호
  • `if (!HM.containsKey(a)) HM.put(a, idx++)`
  • `if (!HM.containsKey(b)) HM.put(b, idx++)`

---

예시

Fred Barney / Barney Betty / Betty Wilma

-> Union-Find는 배열로 관리하기 때문에 숫자 인덱스 필요 (ex. Fred -> 0 / Barney -> 1 / Betty -> 2)

• Fred Barney
  • a = Fred -> X -> {Fred = 0} / idx: 1
  • b = Barney -> X -> {Fred = 0, Barney = 1} / idx: 2
• Barney Betty
  • a = Barney -> O
  • b = Betty -> X -> {Fred = 0, Barney = 1, Betty = 2} / idx = 3
• Betty Wilma
  • a = Betty -> O
  • b = Wilma -> X -> {Fred = 0, Barney = 1, Betty = 2, Wilma = 3} / idx = 4

---

코드

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

// 친구 네트워크
public class boj_4195 {
    static int[] unf, size;

    static int find(int v) {
        if (v == unf[v]) return v;
        return unf[v] = find(unf[v]);
    }

    static int union(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if (fa != fb) {
            unf[fb] = fa;
            size[fa] += size[fb];
        }
        return size[fa];
    }

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

        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            int F = Integer.parseInt(br.readLine());

            unf = new int[F * 2];
            size = new int[F * 2];
            for (int j = 0; j < F * 2; j++) {
                unf[j] = j;
                size[j] = 1;
            }

            Map<String, Integer> HM = new HashMap<>();
            int idx = 0;
            for (int j = 0; j < F; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                String a = st.nextToken();
                String b = st.nextToken();

                if (!HM.containsKey(a)) HM.put(a, idx++);
                if (!HM.containsKey(b)) HM.put(b, idx++);

                int res = union(HM.get(a), HM.get(b));
                sb.append(res).append('\n');
            }
        }

        System.out.println(sb);
    }
}