[JAVA] BOJ 백준 4195번 - 친구 네트워크

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

4195번: 친구 네트워크

---

2. 내가 푼 방법

union-find를 이용하는 것까지는 짐작했지만, 어떻게 기존에 있는 친구 그룹 수를 카운팅해야 할지 감이 잡히지 않았다. 다른 사람 풀이를 보니 새로운 level 배열을 이용해 기존에 존재하던 친구 수를 새로 관계 맺은 그룹의 친구 수에 더해주는 방식임을 이해했다.

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B4195.java

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

class Main {
    static int F;
    static int[] parent, level;
    static Map<String, Integer> map;

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        for (int t = 0; t < T; t++) {
            F = Integer.parseInt(br.readLine());
            parent = new int[2 * F];
            level = new int[2 * F];
            map = new HashMap<>();

            for (int i = 0; i < 2 * F; i++) {
                parent[i] = i;
                level[i] = 1;
            }

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

                if (!map.containsKey(name1)) {
                    map.put(name1, cnt++);
                }
                if (!map.containsKey(name2)) {
                    map.put(name2, cnt++);
                }

                bw.write(union(map.get(name1), map.get(name2))+"\n");
            }
        }

        br.close();
        bw.flush();
        bw.close();
    }

    public static int union(int a, int b) {
        a = getParent(a);
        b = getParent(b);

        if (a > b) {
            parent[b] = a;
            level[a] += level[b];
            return level[a];
        }
        else if (a < b) {
            parent[a] = b;
            level[b] += level[a];
            return level[b];
        }

        return level[a];
    }

    public static int getParent(int x) {
        if (x == parent[x]) return x;
        return getParent(parent[x]);
    }
}

---

4. 결과 및 회고

parent 배열만을 응용하려고 시도했었는데 다른 배열을 생성해 union-find 알고리즘에 올라타 사용되는 것을 보고 반성한 문제이다.