백준 - 4195번 : 친구 네트워크 (C++)

풀이 방법 : 유니온 파인드

문제에서 요구하는 친구 네트워크는 친구 관계만으로 이동할 수 있는 사이라 말했다. 만약 A-B와 B-C가 친구 관계로 주어진다면, A와 C가 B를 통해서 이어져있으므로 하나의 친구 네트워크에 소속되어있다고 할 수 있다.

입력이 주어질 때마다 유니온 파인드를 통해서 집합을 합쳐가면서 입력으로 주어진 유저의 루트 유저의 친구 수를 누적해가면서 카운팅 해주면 된다.
문자열로 입력이 주어지므로 해시 테이블을 사용해주었다.

다 풀고나서 다른 사람들 풀이 찾아보니까 해시 테이블을 사용하되 정수 인덱스로 변환하는 용도로 사용하더라 그렇게 하면 해시테이블은 <string, int> 형태 하나만 두고, int 배열로 친구 숫자를 카운팅 하면되니까 속도면에서나 메모리 면에서나 그렇게 하는게 더 나을거 같다.

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

unordered_map<string, int> mapFriendNum;
unordered_map<string, string> Parent;

const string& GetParent(const string& Input)
{
    if (Parent[Input] == Input)
        return Input;

    else
    {
        Parent[Input] = GetParent(Parent[Input]);
        return Parent[Input];
    }
}

int Connect(const string& Src, const string& Dest)
{
    string SrcParent = GetParent(Src);
    string DestParent = GetParent(Dest);

    if (SrcParent != DestParent)
    {
        mapFriendNum[SrcParent] += mapFriendNum[DestParent];
        Parent[DestParent] = SrcParent;

        return mapFriendNum[SrcParent];
    }

    return mapFriendNum[SrcParent];
}

int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;

    while (N > 0)
    {
        --N;
        int F;
        cin >> F;

        mapFriendNum = unordered_map<string, int>();
        Parent = unordered_map<string, string>();

        for (int i = 0; i < F; ++i)
        {
            string Src, Dest;
            cin >> Src >> Dest;

            if (Parent.find(Src) == Parent.end())
            {
                mapFriendNum.insert(pair<string, int>(Src, 1));
                Parent.insert(pair<string, string>(Src, Src));
            }

            if (Parent.find(Dest) == Parent.end())
            {
                mapFriendNum.insert(pair<string, int>(Dest, 1));
                Parent.insert(pair<string, string>(Dest, Dest));
            }

            cout << Connect(Src, Dest) << '\n';
        }
    }
}