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

WTS·2025년 11월 19일

백준 분리집합 코딩테스트

코딩 테스트

목록 보기

2/81

문제

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다.
우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때,
두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다.

각 테스트 케이스의 첫째 줄에는 친구 관계의 수 $F$ 가 주어지며, 이 값은 $100,000$ 을 넘지 않는다.
다음 $F$ 개의 줄에는 친구 관계가 생긴 순서대로 주어진다.

친구 관계는 두 사용자의 아이디로 이루어져 있으며,
알파벳 대문자 또는 소문자로만 이루어진 길이 $20$ 이하의 문자열이다.

출력

친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

접근 방법

우선 네트워크라고 했기 때문에 그래프나 분리 집합에 대한 문제라고 쉽게 파악할 수 있었고 "두 사람의 친구 네트워크에 몇 명이 있는지" 라는 내용을 읽고 분리 집합의 문제라고 어렵지 않게 파악할 수 있었습니다.

기존의 분리 집합 문제는 각각의 집합에 대해 입력이 숫자 형태로 주어져서 바로 유니온 파인드 로직만 구현하면 문제가 풀리는 구조이지만 해당 문제에서는 친구들을 숫자가 아닌 문자열 형태로 입력이 주어지기 때문에 문자열 입력을 어떻게 숫자로 표현하고 찾을 수 있을지를 고민해야 하는데..

맵을 사용해서
${Key = 문자열, \ Value = \ 해당 \ 이름에\ 대한\ 인덱스}$
를 저장하면 간단히 치환이 가능하겠다고 생각했습니다.

그 이후에는 응용이 거의 필요없는 단순 분리집합 문제로 풀 수 있었습니다.

흐름

문자열을 인덱스로 치환하기 위한 맵, 분리 집합 로직에서 사용되는 parent, size 배열을 선언
한 줄에서 두 명의 이름을 입력 받기 (a와 b)
맵에 이름이 존재하는지 여부에 따라 처리
3-1. 맵에 이름이 없는 경우 : 인덱스는 현재 변수 index 값 할당 (이후 index 증가)
3-2. 맵에 이름이 있는 경우 : 인덱스는 맵에 존재하는 index 값 (map.get(a))
a와 b를 유니온 메서드를 통해 하나의 집합으로 합치고 둘이 해당하는 네트워크 크기 반환 받기

위의 1 ~ 4번의 흐름을 $F$ 번 반복

최적화에 대한 고민

처음의 최적화 방식은 아래와 같습니다.

union은 size를 활용한 최적화 로직, find는 경로 압축 방식으로 최적화
parent와 size는 각 테스트케이스 별 입력으로 들어오는 $F$ 의 $2$ 배 크기로 각각 선언하도록 최적화

처음에는 해당 코드도 효율적이라고 생각했지만 샤워하다가 생각해보니 테스트 케이스 당 가변적인 parent와 size를 재선언해야 하기 때문에 비효율이 발생하겠다고 생각했습니다.

while문마다(테스트케이스 마다) parent와 size 배열의 크기를 $F * 2$ 로 선언하는 것을 볼 수 있습니다.

그냥 $F$ 의 최대 입력 크기의 $2$ 배로 최초 선언을 하고 테스트 케이스 별로 초기화를 해주면 더 효율적이지 않을까? 라는 생각이 문득 들었습니다.

씻고 온 후 코드를 위의 생각대로 고쳤는데 그닥 효율이 개선되지 않은 것 같다는 생각이 들었습니다.
"어차피 테스트 케이스가 끝나면 F의 최대 입력 크기의 2배인 두 배열을 계속해서 초기화 해줘야되는데 이게 개선된 것이 맞나? 라고 생각했는데..

생각해보니 입력되는 $F$ 에 따라 사용되지 않는 공간이 존재한다는 것을 이해하게 되었습니다.
예를 들어 $F$ 의 최대 입력이 $10$ 만이면 parent[200000]으로 선언하고
실제 입력으로 들어온 $F$ 는 $5$ 라면 최대 $10$ 까지 밖에 사용되지 않고 남은 $199990$ 개의 공간을 굳이 초기화를 할 필요가 없다는 것을 인지하게 되었습니다.

현재 코드로서 하나의 테스트케이스에서 사용되는 공간은 변수 index에 따라 정해진다는 것을 파악했고 처음에는 index 만큼만 초기화 하자는 생각을 했지만 현재 코드를 보니 애초에 초기화 같은 것을 할 필요가 없다는 것을 깨닫게 되었습니다.

왜냐하면 $a$ 와 $b$ 로 사용하기로 된 인덱스만을 사용되는 순간 초기화를 하는 구조로 변경했기 때문입니다.

왜 이런 방식을 선택했냐하면 입력받은 $F$ 가 $5$ 라면 변수 index의 최댓값은 $F * 2 - 1$ 인 $9$ 가 되지만 항상 최댓값이 되는 것이 아니고 중복되는 문자열(친구 이름)이 들어온다면 index 값은 그보다 작을 수 있기 때문에 최적화를 위해 사용되지 않는 index가 생기는 문제를 해결하기 위해 일괄 초기화 방식이 아닌 사용되는 인덱스가 발생할 때마다 초기화를 하는 방식으로 구현했습니다.

게다가 해당 문제 특성상 별도의 초기화를 하지 않아도 현재 초기화 방식을 사용한다면 사용하지 않는 공간에 더미 값이 존재할 수는 있지만 그것이 문제를 해결하는데 방해하지 않는다는 것을 깨닫게 되었고 결국 제가 선택한 방식은 다음과 같습니다.

$F$ 로 들어올 수 있는 최댓값에 따른 배열 크기 초기화 방식으로 처음에 parent와 size를 초기화
별도의 초기화 로직을 넣지 않고 사용되는 인덱스마다 초기화

처음 코드

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


class Main {
    static StringTokenizer st;
    static int[] parent;
    static int[] size;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        while (T --> 0) {
            HashMap<String, Integer> map = new HashMap<>();
            int F = Integer.parseInt(br.readLine());
            parent = new int[F * 2];
            size = new int[F * 2];

            int index = 0;
            for (int i = 0; i < F; i++) {
                st = new StringTokenizer(br.readLine());

                String a = st.nextToken();
                String b = st.nextToken();

                if (!map.containsKey(a)) {
                    map.put(a, index);

                    parent[index] = index;
                    size[index] = 1;
                    index++;
                }

                if (!map.containsKey(b)) {
                    map.put(b, index);

                    parent[index] = index;
                    size[index] = 1;
                    index++;
                }

                int network = union(map.get(a), map.get(b));
                sb.append(network).append("\n");
            }
        }
        System.out.print(sb);
    }


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

    static int union (int x, int y) {
        x = find(x);
        y = find(y);

        if (x == y) return size[x];
        
        int sizeX = size[x];
        int sizeY = size[y];

        if (sizeX > sizeY) {
            parent[y] = x;
            return size[x] += size[y];

        }
        else {
            parent[x] = y;
            return size[y] += size[x];
        }
    }
}

최종 코드 (parent, size 초기화 최적화 코드)

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


class Main {
    static StringTokenizer st;
    static int[] parent = new int[200000];
    static int[] size = new int[200000];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        while (T --> 0) {
            HashMap<String, Integer> map = new HashMap<>();
            int F = Integer.parseInt(br.readLine());

            int index = 0;
            for (int i = 0; i < F; i++) {
                st = new StringTokenizer(br.readLine());

                String a = st.nextToken();
                String b = st.nextToken();

                if (!map.containsKey(a)) {
                    map.put(a, index);

                    parent[index] = index;
                    size[index] = 1;
                    index++;
                }

                if (!map.containsKey(b)) {
                    map.put(b, index);

                    parent[index] = index;
                    size[index] = 1;
                    index++;
                }

                int network = union(map.get(a), map.get(b));
                sb.append(network).append("\n");
            }
        }
        System.out.print(sb);
    }


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

    static int union (int x, int y) {
        x = find(x);
        y = find(y);

        if (x == y) return size[x];

        int sizeX = size[x];
        int sizeY = size[y];

        if (sizeX > sizeY) {
            parent[y] = x;
            return size[x] += size[y];

        }
        else {
            parent[x] = y;
            return size[y] += size[x];
        }
    }
}