백준 Gold 2 친구 네트워크

친구 네트워크 (백준 Gold 2)

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

두 명의 친구 관계가 주어졌을 때
해당 친구 그룹의 총 친구수를 출력하는 문제

풀이 방법

주어지는 관계가 '같은 친구 관계'인지를 파악하기 위해
유니온 파인드 (분리 집합)을 사용하면 풀 수 있을것 같았다

따라서
다만 String 데이터로 주어지기에 map을 사용하여
<이름, 부모가 되는 친구>
로 데이터를 구분하였다

• 다만 '해당 그룹'의 친구수를 어떻게 구할까 싶었다
  일반적인 for문 탐색은 지나치게 느릴 것 같았다
  

• 그렇기에 pair<string,int>를 통하여
  추가적으로 ‘부모인 친구’ 와 그룹 개수 를 같이 관리하도록 하였다
  

• 처음에는 <자기 자신, 1>을 데이터로 가지면서
  Union을 통해 그룹 개수를 전달해주는 방식을 통해 문제를 풀었다
  

제출 코드

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

using namespace std;

string FindParent(unordered_map<string, pair<string, int>>& fmap, string x)
{
	if (fmap[x].first == x)
		return x;

	return fmap[x].first = FindParent(fmap, fmap[x].first);
}

bool Union(unordered_map<string, pair<string, int>>& fmap, string a,string b)
{
	a = FindParent(fmap, a);
	b = FindParent(fmap, b);

	if (a == b)
		return false;

	fmap[a].first = b;
	fmap[b].second += fmap[a].second;
	fmap[a].second = 1;
	return true;
}

int main()
{
	
	int t;
	cin >> t;
	while (t > 0)
	{
		int f;
		cin >> f;

		unordered_map<string, pair<string,int>> fmap;

		for (int i = 0; i < f; i++)
		{
			string f1, f2;
			cin >> f1 >> f2;
			if (fmap.find(f1) == fmap.end())
				fmap[f1] = make_pair(f1,1);
			if (fmap.find(f2) == fmap.end())
				fmap[f2] = make_pair(f2, 1);

			Union(fmap, f1, f2);
			cout << fmap[FindParent(fmap, f1)].second << '\n';
		}

		t--;
	}

	return 0;
}

결과

풀이 방법에 대하여 곰곰히 생각하였고
다행히 생각한대로 문제를 풀 수 있었다