b4195. 친구네트워크

 

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

 

 

 

👥 자바로 푸는 친구 네트워크 문제 풀이

 

---

 

📌 문제 개요

 

백준 4195번 - 친구 네트워크 문제는

여러 명이 친구 관계로 연결될 때,

각 관계마다 현재 친구 네트워크의 크기를 출력하는 문제입니다.

 

• 친구 관계가 주어짐 (A B → A와 B가 친구)
• 친구 관계가 생길 때마다, A와 B가 속한 전체 네트워크(연결된 집합)의 크기를 출력
• 이름은 문자열로 주어짐

 

---

 

💡 예제 입력

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

 

예제 출력

2  
3  
4  
2  
2  
4

 

 

---

 

🛠 알고리즘 접근 방식

 

• 핵심은 Union-Find (Disjoint Set) 알고리즘
• 이름이 문자열이기 때문에, HashMap<String, Integer>를 사용하여 문자열을 정수 인덱스로 매핑
• union(a, b) 연산을 할 때마다 두 집합을 병합하고, 병합된 집합의 크기를 반환

 

---

 

✅ 구현 아이디어

 

• p[]: 각 노드의 부모를 저장 (Find 시 사용)
• size[]: 각 집합의 크기 저장 (루트 기준으로만 의미 있음)
• HashMap<String, Integer>: 이름을 정수 인덱스로 매핑
• find(x): 경로 압축 적용
• union(a, b): 더 작은 번호의 루트로 병합하고 크기 업데이트

 

---

 

🧾 코드 해설

// 이름을 정수로 매핑하고 초기화
if (!name.containsKey(a)) name.put(a, count++);
if (!name.containsKey(b)) name.put(b, count++);

// find 함수: 경로 압축 적용
private static int find(int x) {
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

// union 함수: 루트를 기준으로 병합하고 size 업데이트
private static int union(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    if (pa == pb) return size[pa];

    if (pa < pb) {
        p[pb] = pa;
        size[pa] += size[pb];
        return size[pa];
    } else {
        p[pa] = pb;
        size[pb] += size[pa];
        return size[pb];
    }
}

 

 

---

 

✅ 핵심 포인트

 

• 문자열 간의 관계를 수치화하기 위해 HashMap을 사용
• Union-Find + size 배열을 함께 사용해, 집합의 크기를 실시간으로 추적
• 노드 수가 많을 수 있으므로, 충분한 배열 크기 확보 (200_001)
• find()에 경로 압축을 적용하여 성능 향상

 

---

 

✨ 결론: 문자열 문제지만 결국은 그래프 문제

 

이 문제는 입력은 문자열 기반이지만,

실제로는 그래프의 연결 관계와 집합 크기 추적이라는 전형적인 Union-Find 문제입니다.

 

“사람은 문자열이지만, 연결은 수로 모델링한다.”

→ 이처럼 추상적인 개념을 구조화하는 능력이 핵심입니다.