[Baekjoon Online Judge] 4195. 친구 네트워크 // 해설 (Java)

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

 

문제

---

해설

이 문제는 Union-Find 응용 문제입니다.

따라서 Union-Find에 대한 기본적인 지식이 있다고 가정하고 설명하겠습니다.

 

이 문제에서는 단순히 같은 집합에 속하는지를 확인하는 것뿐만 아니라, 집합의 크기도 알아야 하기 때문에 약간의 응용이 필요합니다. 구현 자체는 어렵지 않기 때문에 한 번만 익혀두면 이후에는 쉽게 구현할 수 있습니다.

 

기존에는 루트 노드가 부모를 자기 자신으로 설정하여 자신이 루트임을 표시했습니다.

집합의 크기가 필요한 경우에는 루트의 부모 값에 집합의 크기를 음수로 저장합니다.

그러면 루트 노드의 조건은 부모가 음수인 것이며, 집합의 크기는 루트 노드의 부모 값의 부호를 반대로 바꾼 값이 됩니다.

여기서 음수로 저장하는 이유는 양수인 인덱스들과 구분하기 위해서입니다.

 

그리고 추가적으로 이 문제는 각 사람을 닉네임(문자열)로 표현하기 때문에 Map을 사용해서 각 닉네임을 숫자에 매핑하는 방식을 사용했는데 최선의 방법인지는 잘 모르겠습니다. 이게 구현 난이도를 약간 높인 것 같네요.

---

구현

Code (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

    static int lastIdx = 0;
    static int[] parent = new int[200_000];
    static Map<String, Integer> map = new HashMap<>();

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        for (int testCase = 0; testCase < T; testCase++) {
            map.clear();
            Arrays.fill(parent, -1);

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

            for (int i = 0; i < F; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int[] idxs = new int[2];
                for (int j = 0; j < 2; j++) {
                    String frd = st.nextToken();
                    if (!map.containsKey(frd)) {
                        idxs[j] = lastIdx;
                        map.put(frd, lastIdx++);
                    } else {
                        idxs[j] = map.get(frd);
                    }
                }


                unionSet(idxs[0], idxs[1]);
                int cnt = getSetSize(idxs[0]);

                sb.append(cnt).append('\n');
            }
        }

        System.out.println(sb);
    }

    static void unionSet(int u, int v) {
        int root1 = findSet(u);
        int root2 = findSet(v);
        if (root1 != root2) {
            if (parent[root1] < parent[root2]) {
                parent[root1] += parent[root2];
                parent[root2] = root1;
            } else {
                parent[root2] += parent[root1];
                parent[root1] = root2;
            }
        }
    }

    static int findSet(int v) {
        if (parent[v] < 0) { // this means it's a root node
            return v;
        }
        return parent[v] = findSet(parent[v]);
    }

    static int getSetSize(int v) {
        return -parent[findSet(v)];
    }
}