[BOJ]4195번 : 친구 네트워크

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

4195번: 친구 네트워크

 

분류 : 해싱, 최소 스패닝 트리, 강한 연결 요소, Disjoint-Set, 최대 독립 집합

 

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

class MyScanner {
    BufferedReader br;
    StringTokenizer st;

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

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

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

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }
}

public class Main {

    static PrintWriter out;
    // root[a] = b -> a의 부모는 b이다.
    static int[] root = new int[200001];
    static int[] count = new int[200001];
    public static void main(String[] args) throws IOException {
        MyScanner sc = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));
        int T = sc.nextInt();

        for (int TC = 0; TC < T; TC++)
        {
            int cnt =1;
            int F = sc.nextInt();
            // root 초기화
            for (int i = 1; i <= 2*F; i++)
            {
                root[i] = i;
                count[i] = 1;
            }
            
            Map<String,Integer> map =new HashMap<String,Integer>();
            for(int i=0;i<F;i++)
            {
                String str1 = sc.next();
                String str2 = sc.next();
                if(!map.containsKey(str1))
                {
                    map.put(str1, cnt++);
                }
                if(!map.containsKey(str2))
                {
                    map.put(str2, cnt++);
                }
                out.println(Union(map.get(str1),map.get(str2)));
            }            
        }
        out.flush();
    }

    private static int Union(int a, int b) {
        a = Find(a);
        b = Find(b);
        if (a != b) {
            root[a] = b;
            count[b]+=count[a];
            count[a] = 1;
        }
        return count[b];
    }

    private static int Find(int k) {
        // 루트 노드 이면 return k
        if (k == root[k])
            return k;
        // 그 외에는 자신의 루트를 찾으러 간다.
        return root[k] = Find(root[k]);
    }
}

Union-Find 알고리즘을 써야 하는 것은 알았다.

하지만 입력과 결합 부분을 어떻게 구현 해야 할지 잘 모르겠던 중 Map을 사용하라는 힌트와 대략적인 흐름을 스터디원에게서 들어 방향을 잡게 되었고 문제 해결 성공.

 

근데 혼자서 이걸 생각 해내라고 하면 글쎄.. 잘 모르겠다