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

백준 4195 친구 네트워크

 

4195번: 친구 네트워크

 

문제 설명

 

 - 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하라.

 

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

 

---

 

입력 값

 

 - 첫째 줄에 테스트 케이스 개수가 주어진다. 각 

 

 - 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어진다. 

   ( 0 <= F <= 100,000 )

 

 - 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다.

   친구 관계는 두 사용자의 아이디로 이루어져 있으며,

   알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 두 친구 사이가 주어졌을 때, 해당 친구를 포함한 네트워크에 몇 명이 있는지 판단하는 문제이다.

 

 - 즉, 해당 집합의 인원이 몇 명인지 판단하면 된다.

 

 - 유니온 파인드를 이용하면 이 문제를 간단하게 해결할 수 있다. 

유니온 파인드(Union - Find)

 

 - 기존의 유니온 파인드는 인덱스를 기준으로, 어떤 노드가 어떠한 집합에 포함되어 있는지 판단하.

 

 - 이 문제는 인덱스가 존재하지 않기 때문에, 해당 이름을 인덱스로 변환하고, 저장하는 과정이 필요하다.

   이것은 해쉬맵을 이용하여 간단하게 표현할 수 있다.

 

 - 풀이 과정은 다음과 같다.

   1. 친구 두 명의 이름이 주어진다.

   2. 해당 이름에 맞는 인덱스를 구한다.

   3. 해당 인덱스를 이용하여 union(n1, n2) 연산을 한다.

      이 연산을 하는 과정에서 해당 집합 들 사이에 몇 명이 있는지 저장하여 값을 구한다.

   4. 위 과정을 반복하여 답을 구한다.

 

 - 이 문제에서 주의해야 할 점은 테스트 케이스가 존재하는 것이다.

   유니온 파인드, 해쉬맵을 사용하는 경우 해당 값들을 테스트케이스 마다 초기화 시켜주어야 한다.

 

---

 

 

소스 코드

 

#include <bits/stdc++.h>
#include<unordered_map>
using namespace std;

int friendNum = 0;
unordered_map<string, int> nameToNum;

int parents[200001];
int height[200001];

void initParent() {
	for (int i = 0; i < 200001; i++) {
		parents[i] = i;
		height[i] = 1;
	}
	friendNum = 0;
	nameToNum.clear();
}

int findParent(int n) {
	if (parents[n] == n) {
		return n;
	}
	return parents[n] = findParent(parents[n]);
}

int unionParents(int n1, int n2) {
	int p1 = findParent(n1);
	int p2 = findParent(n2);


	if (p1 < p2) {
		parents[p2] = p1;
		height[p1] += height[p2];
	}
	else if (p1 > p2) {
		parents[p1] = p2;
		height[p2] += height[p1];
		p1 = p2;
	}

	return height[p1];


}


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


	int testCase, friendTotalNum;
	string friendName1, friendName2;

	cin >> testCase;
	for (int t = 0; t < testCase; t++) {

		cin >> friendTotalNum;
		initParent();
		for (int f = 0; f < friendTotalNum; f++) {
			cin >> friendName1 >> friendName2;

			int friendNum1, friendNum2;

			// 없다면
			if (nameToNum.find(friendName1) == nameToNum.end()) {
				friendNum1 = friendNum;
				nameToNum[friendName1] = friendNum;
				friendNum++;
			}
			else {
				friendNum1 = nameToNum[friendName1];
			}

			// 없다면
			if (nameToNum.find(friendName2) == nameToNum.end()) {
				friendNum2 = friendNum;
				nameToNum[friendName2] = friendNum;
				friendNum++;
			}
			else {
				friendNum2 = nameToNum[friendName2];
			}

			cout << unionParents(friendNum1, friendNum2) << "\n";


		}
	}


	return 0;
}