[BOJ] 4195 친구 네트워크 C++

개요

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

4195번: 친구 네트워크

골드2 난이도 문제다.

풀이

문자열과 분리 집합의 형태를 보아하니 유니온 파인드와 map 자료구조로 해결할 수 있을 것 같다고 판단했다.

map[current].id = parent 의 형식으로 데이터를 저장했다.

친구 네트워크가 연결될 때마다 루트 노드의 cnt를 연결된 네트워크의 친구의 수 만큼 증가시켰고, cnt가 낮은 네트워크를 높은 네트워크에 넣도록 했다.

그 후 루트 노드의 cnt를 출력해주면 끝!

 

원래 map으로 구현 했었는데, unordered_map으로 속도를 개선시킬 수 있었다.

map : red-black tree

unordered_map : hash

코드

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;

struct Value
{
	string id;
	int cnt;
};

// key : current_id, value : {parent_id, count}
unordered_map<string, Value> m_parent;

void Init(string id)
{
	if (m_parent[id].cnt) return;
	m_parent[id].id = id;
	m_parent[id].cnt = 1;
}
string Find(string id)
{
	if (m_parent[id].id == id) return id;

	return m_parent[id].id = Find(m_parent[id].id);
}
void Union(string a, string b)
{
	a = Find(a);
	b = Find(b);

	if (a == b) return;

	if (m_parent[a].cnt > m_parent[b].cnt)
		swap(a, b);

	m_parent[b].cnt += m_parent[a].cnt;
	m_parent[a].id = b;
}
void PrintCnt(string id)
{
	id = Find(id);
	cout << m_parent[id].cnt << "\n";
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);

	int T, F;
	string a, b;

	cin >> T;
	while (T--)
	{
		cin >> F;
		while (F--)
		{
			cin >> a >> b;
			Init(a);
			Init(b);
			Union(a, b);
			PrintCnt(a);
		}
		m_parent.clear();
	}
}