[백준] 4195번. 친구 네트워크(JAVA)

문제

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

---

풀이(22분)

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

public class Main {

    static Map<String, Integer> nameToIndex;
    static List<Integer> parent;
    static List<Integer> size;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());
        for (int tc = 0; tc < t; tc++) {
            int f = Integer.parseInt(br.readLine());

            // 초기화
            nameToIndex = new HashMap<>();
            parent = new ArrayList<>();
            size = new ArrayList<>();
            int index = 0;

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

                // 각 이름이 처음 등장하면 초기화
                if (!nameToIndex.containsKey(name1)) {
                    nameToIndex.put(name1, index);
                    parent.add(index);    // 자기 자신이 부모
                    size.add(1);          // 집합 크기 1
                    index++;
                }
                if (!nameToIndex.containsKey(name2)) {
                    nameToIndex.put(name2, index);
                    parent.add(index);
                    size.add(1);
                    index++;
                }

                // 인덱스 추출
                int idx1 = nameToIndex.get(name1);
                int idx2 = nameToIndex.get(name2);

                // 병합
                int mergedSize = union(idx1, idx2);

                // 출력
                System.out.println(mergedSize);
            }
        }
    }

    // Find 연산 (경로 압축)
    static int find(int x) {
        if (parent.get(x) != x) {
            parent.set(x, find(parent.get(x)));
        }
        return parent.get(x);
    }

    // Union 연산
    static int union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        if (rootA != rootB) {
            // 항상 rootA가 작은 인덱스가 되도록
            if (rootA > rootB) {
                int temp = rootA;
                rootA = rootB;
                rootB = temp;
            }

            parent.set(rootB, rootA);
            size.set(rootA, size.get(rootA) + size.get(rootB));
        }

        return size.get(find(a)); // 병합 후 집합 크기 반환
    }
}

---

문제 풀이 전략

 

친구 네트워크라 함은 결국 몇 개의 그룹이 존재하며, 그 그룹에는 몇 명의 사람이 존재하느냐에 대한 문제이다.

 

그렇기에 parent와 size를 따로두고, String을 키로 parent에 대한 idx를 계산하기 위한 map을 별도로 두어 문제를 해결하였다.

즉, 조금 복잡해진 union-find일 뿐 알고리즘을 정확히 이해하고 사용할 수 있다면 그다지 어려운 문제는 아니었다고 생각한다.

[도구정리] Union-Find 알고리즘