[알고리즘/백준] 4195: 친구 네트워크

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

 

1. 문제 접근

 

두 사람을 친구로 만들었을 때, 그들이 속한 그룹(네트워크)의 총 인원 수는 몇 명인가?"를 묻는 문제이다.

 

이 때, 사람을 노드로, 친구 관계를 엣지로 생각한다.

 

친구 네트워크를 구하기 위해선

서로소 집합을 효율적으로 표현하고 관리하는 자료구조인 유니온-파인드 알고리즘을 이용하여 해결할 수 있다!

 

(사람 : 집합의 대표) 구조로 저장하기 위해 map 자료구조를 선택한다.

static std::map<std::string, std::string> parent;

 

또한, 집합에 몇명의 있는지를 저장하기위해 map 자료구조를 하나 더 만든다. (집합의 대표 : 집합에 속한 인원수)

static std::map<std::string, int> network;

 

일반적인 Union-find 알고리즘으로 구현하되,  Union (a,b) 시
    network[b] += network[a];
    network[a] = 0;

함으로서, 인원 수를 관리할 수 있다.

 

 

 

2. 코드

#include <iostream>
#include <vector>
#include <string>
#include <map>

static std::map<std::string, std::string> parent;
static std::map<std::string, int> network;

std::string find(std::string a)
{
    if (a == parent[a])
    {
        return a;
    }
    else
    {
        return parent[a] = find(parent[a]);
    }
}

void unionfunc(std::string a, std::string b)
{
    a = find(a);
    b = find(b);
    parent[a] = b;
    network[b] += network[a];
    network[a] = 0;
}

bool isSameUnion(std::string a, std::string b)
{
    return find(a) == find(b);
}

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

    int n, f;
    std::cin >> n;

    std::string s1, s2;
    while (n--)
    {
        parent.clear();
        network.clear();
        std::cin >> f;
        while (f--)
        {
            std::cin >> s1 >> s2;
            if (parent.find(s1) == parent.end())
            {
                parent[s1] = s1;
                network[s1] = 1;
            }
            if (parent.find(s2) == parent.end())
            {
                parent[s2] = s2;
                network[s2] = 1;
            }

            if (isSameUnion(s1, s2))
            {
                std::cout << network[find(s1)] << "\n";
            }
            else
            {
                unionfunc(s1, s2);
                std::cout << network[find(s1)] << "\n";
            }
        }
    }
}