백준 알고리즘 [유니온파인드] 친구네트워크_4195_골드2

문제

친구네트워크

 

체감 난이도

골드1

 

문제 풀이 소감

매번 테스트 케이스마다 네트워크 활성화 된 친구를 어떻게 계산할지 (key)
- 각 노드별로 크기를 key를 이용해 저장해놓고 union 합산할 때 key도 더해줌

숫자가 아닌 문자열을 어떻게 배열로 관리할 지 (key)
- hashMap을 통해 문자열마다 value (-parent key) 값을 할당해서 필요할 때 꺼내씀

 

코드

public class Main {

    static int[] parents;
    static int[] sizes; // 각 집합의 크기
    static HashMap<String, Integer> nameMap;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder(); // 출력 관리용

        for (int t = 0; t < T; t++) {
            int F = Integer.parseInt(br.readLine());
            parents = new int[F * 2 + 1];
            sizes = new int[F * 2 + 1];
            nameMap = new HashMap<>();

            // 초기화
            for (int i = 0; i <= F * 2; i++) {
                parents[i] = i; // 자기 자신이 부모
                sizes[i] = 1;   // 초기 크기는 1
            }

            for (int i = 0; i < F; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                String name1 = st.nextToken();
                String name2 = st.nextToken();

                int num1 = getNumber(name1);
                int num2 = getNumber(name2);

                // Union 연산으로 연결
                sb.append(Union(num1, num2)).append("\n");
            }
        }
        System.out.print(sb); // 결과를 한 번에 출력
    }

    private static int getNumber(String name) {
        if (!nameMap.containsKey(name)) {
            nameMap.put(name, nameMap.size() + 1);
        }
        return nameMap.get(name);
    }



    private static int Union(int x, int y) {
        x = Find(x);
        y = Find(y);

        if (x != y) {
            if (sizes[x] < sizes[y]) {
                parents[x] = y;
                sizes[y] += sizes[x];
                return sizes[y];
            } else {
                parents[y] = x;
                sizes[x] += sizes[y];
                return sizes[x];
            }
        }
        return sizes[x]; // 이미 같은 집합이라면 크기 반환
    }

    private static int Find(int x) {
        if (x == parents[x]) return x;
        return parents[x] = Find(parents[x]);
    }
}

 

문제 바로가기

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