BOJ - 친구 네트워크(4195)

문제(링크)

유니온-파인드와 해쉬맵을 적절히 사용하여 해결할 수 있는 문제였습니다.

다른 문제들과 다르게 입력값이 문자열로 주어지므로 새로운 이름이 등장할 때마다 각각 index를 부여해 주어야 합니다.

HashMap을 이용하여 index를 부여해 주는데, 이때 중복없이 사람이름이 나오면 총 N * 2명의 사람이 나올 수 있습니다.

따라서 유니온-파인드에서 사용할 parent, p_cnt 배열은 N * 2 개로 선언해 줘야 합니다.

p_cnt[Root] 값은 항상 그 집합의 크기를 나타냅니다.

union 할 때 기존 집합의 p_cnt[Root] 값에 붙는 집합의 p_cnt[Root]값을 더해주면 그 집합의 총 크기를 구할 수 있습니다.

코드

import java.io.*;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {

    public static int N;
    public static HashMap<String, Integer> hm;
    public static int[] parent;
    public static int[] p_cnt;
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] argc) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        for (int i = 0; i < T ; i++) {
            hm = new HashMap<>();
            N = Integer.parseInt(br.readLine());

            parent = new int[N * 2];
            p_cnt = new int[N * 2];

            for (int j = 0; j < N * 2 ; j++) {
                parent[j] = j;
                p_cnt[j] = 1;
            }

            int cnt = 0;
            for (int j = 0; j < N ; j++) {
                st = new StringTokenizer(br.readLine());

                String usr1 = st.nextToken();
                String usr2 = st.nextToken();

                if(!hm.containsKey(usr1)){
                    hm.put(usr1, cnt);
                    cnt++;
                }
                if(!hm.containsKey(usr2)){
                    hm.put(usr2, cnt);
                    cnt++;
                }
                union(hm.get(usr1), hm.get(usr2));
            }
        }
        bw.flush();
        bw.close();
    }
    public static int find(int now){
        if(now == parent[now])
            return now;

        return parent[now] = find(parent[now]);
    }
    public static void union(int x, int y) throws IOException{
        x = find(x);
        y = find(y);

        if(x != y){
            parent[x] = y;
            p_cnt[y] += p_cnt[x];
        }
        bw.write(p_cnt[y] + "\n");
    }
}