[백준] 4195번 : 친구 네트워크 - 자바(Java)

Problem 🔒

문제

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

 

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

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

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

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

출력

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

예제 입력 1

2
3
Fred Barney
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty

예제 출력 1

2
3
4
2
2
4

---

Approach ⭕

1. 문자열(친구 이름) 처리
   • 유니온 파인드 알고리즘은 숫자 인덱스를 기반으로 동작한다.
   • 문자열을 정수 인덱스로 매핑하기 위해서 해시맵을 사용한다.
   • 해시맵의 삽입과 조회의 시간 복잡도는 O(1)이다.
2. 네트워크 내의 친구 수 출력
   • 루트 노드에 집합의 크기(네트워크 내의 친구 수)를 저장하고 반환한다.
   • 두 집합을 합칠 때, 각 집합의 크기를 합하여 저장한다.
   • 각 집합의 크기가 음수로 저장되며, 절대값이 집합의 크기를 의미한다.

---

Solution 💡

public class Main {
    static int F, tree[], idx;
    static HashMap<String, Integer> map = new HashMap<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-->0){
            F = sc.nextInt();
            tree = new int[F*2];
            Arrays.fill(tree, -1);
            map.clear(); // 테케마다 해시맵 초기화
            idx = 0; // 이름과 매핑할 인덱스
            for(int i=0; i<F; i++){
                String f1 = sc.next();
                String f2 = sc.next();
                // 친구 이름 인덱스 매핑
                if(!map.containsKey(f1)) map.put(f1, idx++);
                if(!map.containsKey(f2)) map.put(f2, idx++);
                // 집합의 크기를 sb에 저장
                sb.append(union(map.get(f1), map.get(f2)) + "\\n");
            }
        }//T
        System.out.println(sb);
    }

    public static int find(int x){
        if(tree[x]<=-1) return x;
        return tree[x] = find(tree[x]); // 경로 압축
    }

    public static int union(int a, int b){
        a = find(a);
        b = find(b);
        if(a!=b){ // 두 집합이 서로 다를 때만 수행
            tree[a] += tree[b]; // 집합 크기 증가
            tree[b] = a; // 자식으로 설정
        }
        return -tree[a];
    }
}