[4195번] 친구 네트워크

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Map STL :: http://www.crocus.co.kr/604

2. Union Find(Disjoint Set) :: http://www.crocus.co.kr/683

map과 유니온 파인드를 공부해 보기에 매우 좋은 문제이다.

우리가 현재까지 알고있던 기본적인 맵은 노드의 부모만 이어주지, 그 트리에 존재하는 총 노드의 개수는 알 수 없었다.

이 과정을 유니온 파인드 함수에서 응용할 수 있어야 하고, 이름을 받아온다는 개념을 어떻게 해싱할 지 고려해 볼 수 있어야 한다.

우선적으로 이름을 받아와서 그 이름이 최초 등장인지 아닌지를 확인해야한다.

최초 등장이라면 각 이름에 넘버링을 통해 자신의 고유 번호를 할당시켜준다.(이 과정이 있어야 유니온 파인드와 연계가 된다.)

최초 등장이 아니라면 어짜피 merge에서 루트가 같은 노드였는지, 그게 아니라면 병합을 할 지 고려를 할 수 있다.

그리고 parent 배열을 pair로 바꾸어 second에는 자신의 루트에 총 노드의 개수를 저장 시켜주면서 merge에서 출력을 해준다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <map>
#include <string>
 
#define swap(a,b){int t = a; a = b; b = t;}
 
using namespace std;
 
typedef pair<int, int> pii;
 
int node;
 
// first :: 부모 표현 second :: 자신을 포함한 자식 노드 개수 표현
pii parent[200001];
int level[200001];
 
int find(int u)
{
    // 루트 노드이면 return u
    if (u == parent[u].first)
        return u;
    
    // 그 외에는 자신의 루트를 찾으러 간다.
    return parent[u].first = find(parent[u].first);
}
 
void merge(int u, int v)
{
    u = find(u);
    v = find(v);
 
    // 루트가 같다면 이미 같은 트리
    // 이 때 a b로 입력될 수 있고 b a로 입력될 수 있으니 출력을 해준다. 
    if (u == v)
    {
        printf("%d\n", parent[v].second);
        return;
    }
 
    // u가 v보다 더 깊은 트리라면 swap
    if (level[u] > level[v])
        swap(u, v); // 항상 u가 더 작은 트리가 되도록 한다. 
 
    // u의 루트가 v가 되도록
    parent[u].first = v;
 
    // u와 v의 깊이가 같을 때 v의 깊이를 늘려준다.
    if (level[u] == level[v])
        ++level[v];
 
    // 루트 노드에는 항상 아래 노드의 총 합 개수를 저장해준다고 생각하면
    // 작은 트리에서 큰 트리에 병합될 때 작은 트리 노드 개수를 큰 트리에 더해주면 된다.
    parent[v].second += parent[u].second;
    printf("%d\n", parent[v].second);
}
 
int main()
{
    int n, t, cnt = 1;
    char name1[21], name2[21];
 
    scanf("%d", &n);
 
    while (n--)
    {
        map<string, int> m;
 
        scanf("%d", &t);
 
        for (int i = 0; i < t; i++)
        {
            scanf("%s %s", name1, name2);
 
            if (m[name1] == 0)
            {
                parent[cnt].first = cnt;
                parent[cnt].second = 1;
                level[cnt] = 1;
                m[name1] = cnt++;
            }
 
            if (m[name2] == 0)
            {
                parent[cnt].first = cnt;
                parent[cnt].second = 1;
                level[cnt] = 1;
                m[name2] = cnt++;
            }
            
            merge(m[name1], m[name2]);
        }
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>