💉문제 내용

문제 풀러가기

💉입출력

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

최근에 대회준비때문에 저가 좋아하는 최대유량이나 bfs문제도 풀고있지만,
안풀던 분리집합문제를 풀고있습니다.
분리집합문제는 그래프문제에 비해서 상대적으로 적게 풀었기때문에,
이번에 세그먼트, 구간합문제랑 같이 많이 풀어봐야겠습니다.

💉마치며...

사실 저가 예전에도 언급한 적이있지만,
프로그래밍자체를 시작한건 1년전이지만,
백준문제를 본격적으로 시작한건, 2~3주전입니다.

예전에는 네트워크나 윈도우 프로그래밍같은걸로 삽질 5지게하다가 알고리즘으로 넘어왔습니다.

알고리즘문제를 본격적으로 풀기시작한건 얼마안됬지만,
이번에 대회에서 예선까지라도 통과하고오겠습니다. 화이팅!
(조금만 더 풀면 골드다!!!! 화이팅~~~!!!!)

살짝 tmi지만, 어제 밤새고 엄청 졸린기분으로 아침에 코로나주사맞고왔는데도 3~4시간 쪽잠자고 알고리즘공부....
궁금한 부분있으시면 댓글로 질문주세요~