[백준] 4195번 친구 네트워크

문제: 4195번: 친구 네트워크

 

#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

vector<int> sizes;
vector<int> frendRelation;

int find_set(int u) {
	if (u == frendRelation[u])
		return u;
	else return frendRelation[u] = find_set(frendRelation[u]);
}

void union_(int u, int v) {
	int du = find_set(u); // u 가 속한 집합 번호 가져와
	int dv = find_set(v); // v 가 속한 집합 번호 가져와

	if (du != dv) {
		// du 가 더 큰 트리를 의미할 것임..
		if (sizes[du] < sizes[dv]) swap(du, dv);
		sizes[du] += sizes[dv]; // 더 큰 트리에 작은 트리를 붙이는 거니까 큰 트리에 사이즈에 작은 트리 사이즈 더해주기
		cout << sizes[du] << "\n";
		frendRelation[dv] = du;
	}
	// 만약 이미 두개가 같은 집합에 있으면 둘 중 하나의 사이즈 출력..
	else if (du == dv) cout << sizes[du] << "\n";
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	std::cout.tie(0);

	int t;
	cin >> t;
	while (t-- > 0) {
		vector<pair<string, string>> inputSave;
		map<string, int> stringToInt;

		int f;
		cin >> f; // 친구 관계 수
		int cnt = 0; // 몇명?
		for (int i = 0; i < f; i++) {
			string name1, name2;
			cin >> name1 >> name2;
			pair<string, string> tmp = make_pair(name1, name2);
			inputSave.push_back(tmp);

			
			// 만약 map 에 해당 이름이 존재하지 않으면 새로 추가하기
			if (stringToInt.find(name1) == stringToInt.end()) {
				stringToInt[name1] = cnt++;
			}
			if (stringToInt.find(name2) == stringToInt.end())
				stringToInt[name2] = cnt++;
		}

		sizes = vector<int>(cnt);
		frendRelation = vector<int>(cnt);
		for (int i = 0; i < cnt; i++) {
			sizes[i] = 1; // 각 노드의 처음 사이즈는 1임
			frendRelation[i] = i;
		}

		for (int i = 0; i < f; i++) {
			pair<string, string> tmp = inputSave[i];
			int u = stringToInt[inputSave[i].first];
			int v = stringToInt[inputSave[i].second];
			union_(u, v);
		}
	}


	return 0;
}

 

입력이 숫자로 주어졌다면 쉽게 풀 수 있는데 아쉽게도 문자열로 주어지는 문제였다. 이를 위해서 문자열을 정수에 매핑시키는 과정이 필요했다.

 

매핑 시키기 위해서는 map 이라는 stl 을 이용해야 한다. 이는 해당 키 값에 value 를 대응시키는 자료구조 인 것 같던데..

아무튼 이름을 입력받을 때마다 이게 이미 존재하는 이름인지 아닌지를 판단하기 위해 find 라는 함수를 이용한다. 만약 존재하지 않는다면 반환값이 해당 map 의 end 와 같으므로 이를 조건문에 이용해서 판별해주면 된다.

 

그래서 맵에 존재하지 않는다면 새로 추가해주면 된다.

 

 그 다음부터는 그냥 1717번 처럼 문제를 해결해주면 되는데 다른 점이 size 를 출력해야 한다는 것이다.

사이즈는 말그대로 특정 트리의 사이즈를 의미한다. 만약 두개의 트리를 합치려고 할 때 더 큰 트리에 작은 트리를 합쳐야 하는데 이때 큰 트리의 사이즈에 작은 트리의 사이즈를 더해주면 된다.

 

만약 두 노드가 같은 집합에 존재한다면 find_set 함수를 이용했을 때 같은 값을 반환받을 것이므로 둘 중 하나로 sizes 에 접근해서 값을 가져온 후 출력해주면 된다.

 

 

 

참고자료:

1. map

[C++][STL] map 사용법 정리

[C++][STL] map 사용법 정리

 

2. 문제

[백준] 4195번 - 친구 네트워크 | ChanBLOG

[백준] 4195번 - 친구 네트워크