[BOJ] 4195 : 친구 네트워크

Drakk·2021년 7월 23일

C boj 분리집합 알고리즘 유니온파인드

알고리즘 문제풀이

목록 보기

8/22

💉문제 내용

문제 풀러가기

💉입출력

🧺입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 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

💉문제 분석

🔋분류

분리집합, 해쉬

🔋난이도

골드II

💉문제 풀이

🔋해법

이 문제는 해쉬랑 분리집합을 섞은문제입니다.
해법은 간단합니다.
입력으로 들어오는 친구들중에서 알려진친구가 아니면, 그 친구이름으로 숫자가 들어갑니다.
이 숫자는 매번 1씩증가하며, 알려진 친구라면 그냥 그대로 쭉 갑니다.

어차피 다음에가서 [] 연산자로 해당 key에맞는 value를 찾으면 되니까요.

모든 정보를 갱신했다면, 두 집합을 합쳐줍니다.
그다음 결과값은 각각 가지고있는 친구들의 수가 적혀진 배열의 입력한 a또는 b의 부모노드번째인덱스가 됩니다.

🔋소스코드

#include <bits/stdc++.h>

constexpr int MAX = 1000000;

int parent[MAX], fcount[MAX];

int getParent(int value) {
	if (parent[value] == value) return value;
	return parent[value] = getParent(parent[value]);
}

void Union(int a, int b) {
	int xa = getParent(a);
	int xb = getParent(b);
	if (xa < xb) {
		parent[xb] = xa;
		fcount[xa] += fcount[xb];
	}
	else if (xb < xa) {
		parent[xa] = xb;
		fcount[xb] += fcount[xa];
	}
}

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

	int T, M;

	std::cin >> T;
	for (int k = 0; k < T; ++k) {
		int count = 0;
		std::map<std::string, int> m;

		std::cin >> M;

		for (int i = 0; i < MAX; ++i) {
			parent[i] = i;
			fcount[i] = 1;
		}

		for (int j = 0; j < M; ++j) {
			int sa, sb;
			std::string a, b;
			std::cin >> a >> b;
			auto it1 = m.find(a);
            
            		//만약 알려지지않은 친구라면
			if (it1 == m.end()) m[a] = count++;

			auto it2 = m.find(b);
            
            		//만약 알려지지않은 친구라면
			if (it2 == m.end()) m[b] = count++;

			Union(m[a], m[b]);

			std::cout << fcount[getParent(m[a])] << '\n';
		}
	}
}