백준 4195 (골드 2) 친구 네트워크 - 분리 집합 (Union Find)

 

 

해당 문제는 그래프 탐색(DFS, BFS), 분리 집합을 활용해서 풀 수 있지만 그래프 탐색의 경우 시간 제한이 걸릴 수 있습니다.

 

만약 그래프로 푼다면 O(T * F * F)만큼이 걸릴 것 입니다. F의 최대 값이 100,000인데  F * F 라니 너무하지 않나요?

 

그래서 우리는 다른 방법을 찾아야 합니다.

 

바로 분리집합(Union Find) 입니다.

Union Find란 그래프에서 어떠한 정점들이 연결되어 있는지를 알고 싶을 때 사용한다고 생각하시면 되겠습니다.

 

아래에는 두 집합이 있습니다.

 

김병만 팀장의 팀원 ->  수아, 민지

박지원 팀장의 팀원 ->  종원, 민재

 

만약 수아와 민지가 같은 팀인지  종원과 민지는 같은 팀이 아닌지 컴퓨터는 어떻게 알 수 있을까요?

우리는 눈으로 단 번에 판단 할 수 있습니다. 하지만 팀원이 1 만명 10 만명이라면 눈으로 판단 할 수 있을까요?

 

Union Find 알고리즘에서는 팀장(Root)을 보고 같은 팀인지를 파악합니다. 

수아의 root는 병만이고 민재의 root는 지원입니다. 서로 다른 root를 가졌으니 다른 집합인 것을 알 수 있습니다.

 

그리고 Union Find에서는 집합을 합치는 것도 간단합니다. 

만약 병만이와 지원이의 팀을 합친다고 생각 해 봅시다.

 

하나의 집합을 다른 하나의 root를 가르치도록 변경하면 하나의 집합으로 합쳐지게 됩니다.

 

 

아래는 풀이 코드입니다.

#include <iostream>
#include <map>

using namespace std;


string findRoot(map<string, string>& hash, string& str)
{
    if (hash.find(str) == hash.end())
    {
        return str;
    }

    return hash[str] = findRoot(hash, hash[str]);
}

int main()
{
    int t, n;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> t;

    string str1, str2;

    while (t--)
    {
        cin >> n;

        map<string, string> friends;

        map<string, int> counter;

        while (n--)
        {
            cin >> str1 >> str2;

            if (counter.find(str1) == counter.end())
            {
                counter[str1] = 1;
            }

            if (counter.find(str2) == counter.end())
            {
                counter[str2] = 1;
            }

            string root1, root2;

            root1 = findRoot(friends,str1);
            root2 = findRoot(friends, str2);


            if (root1 != root2)
            {
                friends[root2] = root1;
                counter[root1] += counter[root2];
            }

            cout<< counter[root1] << "\n";
        }

    }
}