[c++] 백준 4195: 친구 네트워크

4195번: 친구 네트워크

💡 문제

👀 코드

/**
 * baekjoon - 4195
 * hashmap, union-find
 */

#include <iostream>
#include <map>
#define fio ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;

map<string, int> list;
int parent[200001];
int friend_num[200001];

int find_parent(int x){
    if (parent[x] == x) return x;

    return parent[x] = find_parent(parent[x]);
}

void make_union(int a, int b){
    a = find_parent(a);
    b = find_parent(b);

    if (a < b){
        parent[b] = a;
        friend_num[a] += friend_num[b];
    }

    else if (b < a){
        parent[a] = b;
        friend_num[b] += friend_num[a];
    }
}

int main(){
    fio;
    //input
    int testcase; cin >> testcase;
    string a, b;
    int n, cnt;

    for (int t = 0; t < testcase; t++){
        // clear
        cnt = 0;
        list.clear();
        for (int i = 0; i < 200001; i++){
            parent[i] = i;
            friend_num[i] = 1;
        }
        cin >> n;
        int x, y;
        for (int i = 0; i < n; i++){
            cin >> a >> b;

            if (list.find(a) == list.end()) {
                list[a] = ++cnt;
                x = cnt;
            }
            else {
                x = list.find(a)->second;
            }

            if (list.find(b) == list.end()) {
                list[b] = ++cnt;
                y = cnt;
            }
            else {
                y = list.find(b)->second;
            }

            make_union(x, y);

            int root = find_parent(x);
            cout << friend_num[root] << "\n";
        }
    }

    return 0;
}

📌 해설

해당 문제를 풀기 위해서는 분리 집합(Disjoint Set)의 개념을 알고 가야한다.

Disjoint Set

서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조

Union-Find

Disjoint Set을 표현할 때 사용하는 알고리즘으로, 세 가지 연산을 이용함

1. make-set(x)
   • 초기화
   • x를 유일한 원소로 하는 새로운 집합을 구성
2. union(x, y)
   • 합치기
   • x가 속한 집합과 y가 속한 집합을 합침
3. find(x)
   • 찾기
   • x가 속한 집합의 루트 노드 값을 반환

기본 구현 방법은 다음과 같다.

참조

/* 초기화 */
int root[MAX_SIZE];
for (int i = 0; i < MAX_SIZE; i++)
    parent[i] = i;

/* find(x): 재귀 이용 */
int find(int x) {
    // 루트 노드는 부모 노드 번호로 자기 자신을 가진다.
    if (root[x] == x) {
        return x;
    } else {
        // 각 노드의 부모 노드를 찾아 올라간다.
        return find(root[x]);
    }
}

/* union(x, y) */
void union(int x, int y){
    // 각 원소가 속한 트리의 루트 노드를 찾는다.
    x = find(x);
    y = find(y);

    root[y] = x;
}

---

분리 집합의 개념을 가지고 해당 문제를 다음 순서처럼 풀어나갈 수 있다.

1. 초기화
2. 친구 관계 입력 값을 받아 해당 사람이 map에 존재 시 찾아서 서로 연결
3. 존재 하지 않으면 새로 map에 추가하고 정보 등록

1. 초기화

   테스트 케이스가 여러 개 존재하기 때문에 사용하는 자료구조에 담긴 정보를 초기화해줄 필요가 있다. 따라서 사용하는 parent[], friend_num[], list을 모두 초기화 해준다. 그리고 사용하는 변수 cnt도 0으로 다시 초기화 해준다.

   // clear
   cnt = 0;
   list.clear();
   for (int i = 0; i < 200001; i++){
   	parent[i] = i;
     friend_num[i] = 1;
   }

2. 친구 관계 입력 값을 받아 map에서 찾기

   map에 내장되어 있는 함수 find를 이용해 친구의 이름을 key로 하여 map에서 찾는다. 해당 정보가 없으면 end 위치를 찍어주는 것을 활용한다.

3. 존재하지 않을 때

   map에 해당 정보를 추가해주고, cnt 변수를 1늘려 정보에 입력한다.

4. 존재할 때

   map에서 해당 친구의 정보를 불러온다.

5. 분리 집합 연산 함수

   int find_parent(int x){
       if (parent[x] == x) return x;
   
       return parent[x] = find_parent(parent[x]);
   }
   
   void make_union(int a, int b){
       a = find_parent(a);
       b = find_parent(b);
   
       if (a < b){
           parent[b] = a;
           friend_num[a] += friend_num[b];
       }
   
       else if (b < a){
           parent[a] = b;
           friend_num[b] += friend_num[a];
       }
   }

   • make_union 함수 : union 시킬 때, 두 사람의 친구 수를 불러와서 더 많은 쪽의 친구의 수를, 수가 더 작은 쪽에 더한다.
   • find_parent 함수 : parent 배열에서 해당 부모 노드가 누구인지 구하는 함수이다.