[백준/C++] 4195. 친구 네트워크

문제

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

4195번: 친구 네트워크

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

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

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

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

출력

친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

예제 입력

2

3

Fred Barney

Barney Betty

Betty Wilma

3

Fred Barney

Betty Wilma

Barney Betty

예제 출력

2

3

4

2

2

4

 

풀이

Union- Find 알고리즘 이용 

문제에서 원하는 것이 네트워크의 크기 이기 때문에, parent배열 이외에 sizes배열도 이용하였다.

 

두 친구의 이름을 입력받은 뒤, 

최초 input이면 초기화를 해주고,

두 친구를 Union해준다. 

 

그 뒤에 각각 두 친구의 부모를 Find하고, p1과 p2의 size를 비교해서 더 큰 숫자를 print한다. 

코드

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

#define endl '\n'
using  namespace std;

unordered_map<string, string> parent; // <이름, 부모 이름>
unordered_map<string, int> sizes; // <이름, 크기>

// 유니온-파인드
string Finds(string f1) {
	if (parent[f1] == f1) return f1;
	return parent[f1] = Finds(parent[f1]);
}
void Union(string f1, string f2) {
	f1 = Finds(f1);
	f2 = Finds(f2);

	if (f1 != f2) {
		if (sizes[f1] < sizes[f2]) {
			sizes[f2] += sizes[f1];
			parent[f1] = f2;
		}
		else {
			sizes[f1] += sizes[f2];
			parent[f2] = f1;
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	int T; cin >> T;
	for (int t = 0;t < T;t++) {
		int F; cin >> F;
		parent.clear();
		sizes.clear();
		for (int f = 0;f < F;f++) {
			string f1, f2; cin >> f1 >> f2;
			if (parent.count(f1) == 0) { // 최초입력시
				parent[f1] = f1;
				sizes[f1] = 1;
			}
			if (parent.count(f2) == 0) { // 최초입력시
				parent[f2] = f2;
				sizes[f2] = 1;
			}
			Union(f1, f2); // 두 친구 연결
			
			string p1 = Finds(parent[f1]);
			string p2 = Finds(parent[f2]);

			int result = (sizes[p1] > sizes[p2]) ? sizes[p1] : sizes[p2];
			cout << result << endl;
		}
	}
	return 0;
}

결과