문제

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

문제 링크

풀이

그 저 뭐야
입력으로 주어지는게 사람의 이름(string)이다보니 인덱스로 바로 활용하기 어려웠다.
그때문에 사전형 자료형이 필요하여 unordered_map을 활용했다.

친구를 건너 건너 갈 수 있다는 것은 이어져있는 친구끼리 같은 집합에 속하는 것을 의미한다.
이를 union-find 알고리즘을 이용하여 해결했다.

친구 네트워크의 친구의 수를 구하기 위해서는 각 집합의 속한 원소들의 수를 세면 되는데 이를 위해 매번 하나 하나 세는 것은 매우 비효율적이다.
rank, root처럼 미리 size라는 변수를 만들어 집합의 원소의 개수를 세어 저장해두면 매번 모든 원소를 순회하며 비효율적으로 구할 필요 없이 상수시간에 원소의 개수를 얻을 수 있다.
두 집합이 합쳐질 경우에 root가 되는 노드의 size에 두 집합의 원소의 개수를 더해 저장하면 된다.

코드

#include <iostream>
#include <unordered_map>

using namespace std;

struct Node{
    string name;
    string root;
    int depth;
    int size;
};

unordered_map<string, Node> Network;

Node makeSet(string name){
    Node x;
    x.name = name;
    x.root = name;
    x.depth = 0;
    x.size = 1;

    return x;
}

string findSet(const string& person){
    Node& x = Network[person];
    if (x.root == x.name){
        return x.name;
    }
    else{
        x.root = findSet(x.root);
        return x.root;
    }
}

void unionSet(string p1, string p2){
    p1 = findSet(p1);
    p2 = findSet(p2);

    Node& x = Network[p1];
    Node& y = Network[p2];

    if (x.name == y.name) return;

    if (x.depth > y.depth){
        y.root = x.name; // y.root = x.root;
        x.size += y.size;
    }
    else if (x.depth < y.depth){
        x.root = y.name;
        y.size += x.size;
    }
    else{
        x.root = y.name;
        y.size += x.size;

        y.depth++;
    }
}

int main(){
    cin.tie(0);
	ios_base::sync_with_stdio(false);

    int n, f;

    cin >> n;
    while (n--){
        cin >> f;
        for (int i=0; i < f; i++){
            string p1, p2;
            cin >> p1 >> p2;
            
            if (Network.find(p1) == Network.end()) Network[p1] = makeSet(p1);
            if (Network.find(p2) == Network.end()) Network[p2] = makeSet(p2);
            unionSet(p1, p2);

            cout << Network[findSet(p1)].size << "\n";
        }
        Network.clear();
    }

    return 0;
}