[백준] 4195 친구 네트워크

Union-Find 자료구조 참고자료
https://chanhuiseok.github.io/posts/improve-7/

풀이

이 문제는 Union-Find 자료구조를 사용하여 해결하였습니다. 다만 Union-Find는 숫자를 기준으로 사용됩니다. 그래서 이 문제에서는 연결 관계를 문자열로 주고 중복된 문자열도 생각해야 하므로 HashMap을 사용하였습니다.

원소 x의 대푯값을 반환하는 함수

 public static int find_parent(int x) {
        if (x == parent[x]) return x;
        return parent[x] = find_parent(parent[x]);
 }

더 큰 부모로 union을 합치는 함수

 public static void union_unite(int a, int b) {
        a = find_parent(a);
        b = find_parent(b);
        if (a < b) {
            parent[b] = a;
            friend_cnt[a] += friend_cnt[b];
        } else if (a > b) {
            parent[a] = b;
            friend_cnt[b] += friend_cnt[a];
        }
  }

코드

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

public class Main {
    static int[] parent;
    static int[] friend_cnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); //테스트 케이스

        for (int i = 0; i < T; i++) {
            int F = Integer.parseInt(br.readLine());
            parent = new int[F * 2];
            friend_cnt = new int[F * 2];
            HashMap<String, Integer> map = new HashMap<>();
            Arrays.fill(friend_cnt, 1); //수를 1로 초기화

            int idx = 0;
            for (int f = 0; f < F; f++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                String str1 = st.nextToken();
                String str2 = st.nextToken();
                // 처음 이면 HashMap에 put
                if (!map.containsKey(str1)) {
                    parent[idx] = idx;
                    map.put(str1, idx++);
                }
                if (!map.containsKey(str2)) {
                    parent[idx] = idx;
                    map.put(str2, idx++);
                }
                //union으로 연결
                union_unite(map.get(str1), map.get(str2));
                //find하여 저장된 cnt값 출력
                System.out.println(friend_cnt[find_parent(map.get(str2))]);
            }
        }
    }

    public static int find_parent(int x) {
        if (x == parent[x]) return x;
        return parent[x] = find_parent(parent[x]);
    }

    public static void union_unite(int a, int b) {
        a = find_parent(a);
        b = find_parent(b);
        if (a < b) {
            parent[b] = a;
            friend_cnt[a] += friend_cnt[b];
        } else if (a > b) {
            parent[a] = b;
            friend_cnt[b] += friend_cnt[a];
        }
    }
}