[Baekjoon,4195] 친구 네트워크

Union-Find 알고리즘을 이용하여 해결했다. 이는 상호 배타적 집합을 만들어 내는 자료구조이다. 자료구조에 대한 설명은 Heee’s 블로그에서 볼 수 있다.

문제에서 이 알고리즘을 이용하면 네트워크로 연결된 친구들을 같은 집합에 묶을 수 있다. 이때 집합의 rank는 있으나 각 집합의 원소의 개수는 없으므로 이를 추가적으로 구현하여 이 문제를 해결하였다. 나는 이를 두 집합을 합칠 때 집합의 원소의 크기를 반환하는 방식으로 구현했다.

구현

구현 시 각 집합에 문자열로 접근하지 않고 map을 이용하여 각 이름마다 인덱스를 부여하여 집합에 접근했다. 주의 할 사항은 입력, 출력 값이 많기 때문에 입출력이 빠른 함수를 이용하여야 한다는 것이다.

#include <iostream>
#include <vector>
#include <map>
using namespace std;

const int MAX=200000;

struct DisjointSet
{
    vector<int> parent,rank,count;
    DisjointSet() : parent(MAX), rank(MAX,-1), count(MAX,1) 
    { 
        for(int i=0;i<MAX;++i)
            parent[i]=i;
    }
    int find(int n)
    {
        if(parent[n]==n)
            return n;
        return parent[n]=find(parent[n]);
    }
    int merge(int a, int b)
    {
        a=find(a); b=find(b);
        
        if(a==b)
            return count[a];
        if(rank[a]>rank[b])
            swap(a,b);
        parent[a]=b;
        if(rank[a]==rank[b])
            ++rank[b];
        
        count[b]+=count[a];
        return count[b];
    }
};

int main()
{
    int testCase;
    cin>>testCase;
    while(testCase--)
    {
        int n, idx=0;
        cin>>n;
        
        DisjointSet network;
        map<string,int> order;
        for(int i=0;i<n;++i)
        {
            char tmp1[21], tmp2[21];
            scanf("%s %s",tmp1,tmp2);
            
            string a=tmp1, b=tmp2;
            
            if(order.find(a)==order.end())
                order.insert(make_pair(a,idx++));
            if(order.find(b)==order.end())
                order.insert(make_pair(b,idx++));
            
            printf("%d\n",network.merge(order[a],order[b]));
        }
    }

    return 0;
}