BOJ - 친구 네트워크 4195번 (JAVA)

❓ 문제 - 백준 친구 네트워크 4195번 - JAVA 풀이법

 

출처 

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

4195번: 친구 네트워크

 

 

📝 문제해결법

1. 문제

• 친구 관계가 주어질 때 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 문제이다.

 

2. 해결 방법

• 우선, 두 친구 관계가 주어질 때 두 친구가 자신이 친구 네트워크를 통해 한 네트워크에 속하는지 아니면 다른 네트워크인지 분류해야 하므로 union find 사용하면 된다.
• 따라서 원래 같은 네트워크에 속했다면 기존 그 네트워크에 속한 사람의 수를 출력하면 되고, 만약 다른 네트워크라면 하나의 네트워크로 합치고 두 네트워크에 속한 사람의 수의 합을 출력하면 된다.
• 하지만 문제에서 친구 관계를 줄 때 문자열 형태로 주기 때문에, 기존에 union find 방법에서 해당 parent를 관리할 때 우선 사람의 이름에 인덱스를 부여할 hashmap을 사용한다.
• 해당 사람을 접근할 때 문자열 -> 인덱스 변환해서 기존 union find로 접근하면 된다.
• 그리고 해당 네트워크에서 사람이 몇 명 들어 있는지를 저장하는 자료구조를 cnt를 사용한다.
• 문제 풀이 내에서는 number로 해당 사람이 몇 번 인덱스인지 저장하고, cnt로 속한 네트워크에 사람이 몇 명 속했는지 저장한다.
• 그리고 친구 관계가 주어지면 둘이 같은 네트워크인지 find_parent로 부모 노드의 인덱스로 비교해서 같은 네트워크라면 해당 네트워크에 속한 사람의 수를, 다른 네트워크라면 두 네트워크를 union 하고 두 네트워크의 속한 사람의 수의 합을 출력한다.

 

3. 느낀점

• 우선 문제를 이해하는데 조금 시간이 걸렸지만 union find라는 것을 생각하니 입력과 출력형태로 어떻게 풀어야하는지 유추 가능했다.
• 하지만 첫 시도에 parent를 계산하는데도 int 배열이 아닌 모두 다 string 형태로 접근해서 부모 노드를 찾도록 구현했더니 44퍼에서 시간초과가 발생했다. 코드를 계속 보다가 문자열 기준으로 union find 하다보면 문자열 비교 연산에 들어가는 시간이 많이 소요될 것 같아서 위 방식대로 사람에 맞는 인덱스를 부여하고 인덱스를 기준으로 union find 하니깐 통과가 됐다.
• 그리고 두 번째 이슈는 위 방식대로 풀었는데 자꾸 런타임 에러로 배열 인덱스 초과가 떠서 계속 고민하니 처음에 parent int 배열을 문제에서 주어진 범위 100001로 잡았는데 이 범위는 사람 명 수의 최대 범위가 아니고 친구 관계의 최대 범위라서 x2를 해주고 푸니 잘 통과했다 !
• 오랜만에 코드 내에서 고민하면서 시간초과를 해결하니 아주 뿌듯 했다... 알고리즘.. 재밌어..

 

💻 소스코드 (JAVA)

// BOJ - 친구 네트워크(4195번)
// Union Find
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    public static int f, n;
    public static int INF = (int)1e9;
    public static int[] parent;
    public static HashMap<String, Integer> number;
    public static HashMap<Integer, Integer> cnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;
        f = Integer.parseInt(br.readLine());

        for(int test_case=1;test_case<=f;test_case++){
            n = Integer.parseInt(br.readLine());
            number = new HashMap<>();
            cnt = new HashMap<>();
            parent = new int[200001];
            for(int i=0;i<200001;i++){
                parent[i] = i;
            }

            int num = 0;
            for(int i=0;i<n;i++){
                st = new StringTokenizer(br.readLine(), " ");
                String a = st.nextToken();
                String b = st.nextToken();
                if(!number.containsKey(a)){
                    number.put(a, ++num);
                    cnt.put(num, 1);
                }

                if(!number.containsKey(b)){
                    number.put(b, ++num);
                    cnt.put(num, 1);
                }

                int p_a = find_parent(number.get(a));
                int p_b = find_parent(number.get(b));
                if(p_a != p_b){
                    sb.append(cnt.get(p_a)+cnt.get(p_b)+"\n");
                    union_find(p_a, p_b);
                } else {
                    sb.append(cnt.get(p_a)+"\n");
                }

            }
        }
        System.out.println(sb.toString());
    }

        public static int find_parent(int i) {
        if(parent[i] == i) return i;
        return parent[i] = find_parent(parent[i]);
    }

    public static void union_find(int a, int b) {
        cnt.put(a, cnt.get(a)+cnt.get(b));
        parent[b] = a;
    }

}