백준 4195 - 친구 네트워크

Minjae An·2023년 8월 14일

ps 분리집합 유니온 파인드

PS

목록 보기

33/143

문제

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];
    }
}