백준 4195 - 친구 네트워크

문제

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

리뷰

유니온 파인드 로직을 이용하여 풀이할 수 있는 문제였다.

최적화된 유니온 파인드의 parent 배열은 parent[i]가 음수일 때 그 절댓값이
i를 루트로 하는 집합의 노드 수를 표현할 수 있으므로 들어오는 관계를 유니온 파인드
연산을 통하여 분리 집합으로 표현해준 뒤 루트 노드의 parent[i]값을 기록해주는 식으로
로직을 구성하였다. 한편, 문자열 데이터를 통해 노드를 표현하기에 문자열과 인덱스를
매핑할 수 있도록 Map<String, Integer> 를 활용하였다.

주의할 점은 주어지는 F가 친구 관계의 수를 나타내지 총 인원 수를 나타내지 않기
때문에 parent 배열의 길이를 유의해서 설정해야 한다는 점이었다.
F개의 관계가 주어질때 각 관계를 이루는 인원이 전부 다르다면 가능한 최대 인원수는
$2 \times F$이다. 이 부분으로 인해 인덱스 예외가 발생하여 잠시 난항을 겪었다.

로직의 시간 복잡도는 유니온 파인드의 시간 복잡도로 수렴하며 이는 $O(a(F))$이다.
따라서 $F$의 최대값인 10만일 때도 주어진 제한 조건인 3초를 무난히 통과한다.

코드

import java.util.*;

import static java.lang.Integer.parseInt;

public class Main {
    static int[] parent;
    static Map<String, Integer> indexMap = new HashMap<>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = parseInt(in.nextLine());

        StringBuilder sb = new StringBuilder();
        StringTokenizer st;


        while (T-- > 0) {
            int n = parseInt(in.nextLine());
            parent = new int[2*n];
            Arrays.fill(parent, -1);

            int idx = 0;

            while (n-- > 0) {
                st = new StringTokenizer(in.nextLine());
                String u = st.nextToken();
                if (indexMap.get(u) == null)
                    indexMap.put(u, idx++);

                String v = st.nextToken();
                if (indexMap.get(v) == null)
                    indexMap.put(v, idx++);

                int count = -union(indexMap.get(u), indexMap.get(v));
                sb.append(count + "\n");
            }
        }

        System.out.print(sb);
        in.close();
    }

    static int find(int u) {
        if (parent[u] < 0) return u;

        return parent[u] = find(parent[u]);
    }

    static int union(int u, int v) {
        int root1 = find(u);
        int root2 = find(v);

        if (root1 == root2) return parent[root1];

        int root;

        if (parent[root1] < parent[root2]) {
            parent[root1] += parent[root2];
            parent[root2] = root1;
            root = root1;
        } else {
            parent[root2] += parent[root1];
            parent[root1] = root2;
            root = root2;
        }

        return parent[root];
    }
}

결과

참고

위 유니온 파인드 로직에 대한 자세한 설명이 필요하면 아래 링크를 참고하자.
https://velog.io/@mj3242/%EB%B0%B1%EC%A4%80-7511-%EC%86%8C%EC%85%9C-%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%82%B9-%EC%96%B4%ED%94%8C%EB%A6%AC%EC%BC%80%EC%9D%B4%EC%85%98