🧪백준 4195 - 친구 네트워크

 

 

Tier : Gold 2

---

각 친구를 정수 인덱스로 매핑한 후, find 메서드로 루트를 찾고, union 메서드로 두 네트워크를 합칩니다.

경로 압축과 union - size 기법을 사용하여 효율적으로 구현하였습니다.

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

public class Main {
    // 각 친구 네트워크의 대표와 모임의 크기를 저장하는 배열
    static int[] parent, size;
    
    // find : 친구 네트워크의 대표(그룹의 시작)를 찾는 함수
    static int find(int a) {
        // a가 자기 자신이면 대표이므로 a를 반환
        // 아니면, a의 대표를 찾아서 a의 부모로 저장하고 반환
        return parent[a] == a ? a : (parent[a] = find(parent[a]));
    }
    
    // union 함수: 두 친구 네트워크의 그룹을 하나로 합치고, 합친 그룹의 크기를 반환
    static int union(int a, int b) {
        a = find(a); 
        b = find(b);
        // 이미 같은 그룹에 있으면 그냥 해당 네트워크 그룹의 크기를 반환
        if(a == b) return size[a];
        // 작은 그룹을 큰 그룹에 합치기 위해 크기를 비교
        if(size[a] < size[b]) { 
            int tmp = a; 
            a = b; 
            b = tmp; 
        }
        // b의 그룹을 a의 그룹에 합침
        parent[b] = a;
        size[a] += size[b];
        return size[a];
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine());
        
        while(T-- > 0) {
            int F = Integer.parseInt(br.readLine());
            // 최대 2*F명의 친구를 저장할 수 있도록 배열 새엉
            parent = new int[2 * F];
            size = new int[2 * F];
            for (int i = 0; i < 2 * F; i++) {
                parent[i] = i; // 친구 네트워크의 본인이 대표
                size[i] = 1;   // 친구 네트워크의 크기는 처음에 1명
            }
            
            // Map으로 친구 이름을 숫자로 바꿔서 관리하기 위해 HashMap사용
            Map<String, Integer> map = new HashMap<>();
            int idx = 0; // 새로운 친구가 나오면 순서대로 번호를 붙여요.
            
            for (int i = 0; i < F; i++) {
                String[] s = br.readLine().split(" ");
                // 친구 이름이 처음 나오면 인덱스 ++
                if (!map.containsKey(s[0])) map.put(s[0], idx++);
                if (!map.containsKey(s[1])) map.put(s[1], idx++);
                // 두 친구의 그룹을 합친 후, 합쳐진 그룹의 인원 수를 결과에 추가
                sb.append(union(map.get(s[0]), map.get(s[1]))).append("\n");
            }
        }
        System.out.print(sb);
    }
}