백준 4195: 친구 네트워크

문제 요약

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

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

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

문제 분류

• 자료 구조
• 해시를 사용한 집합과 맵
• 분리 집합

문제 풀이

어떠한 문자열로 친구를 2명 입력 받아서, 이 친구가 구성된 집합 원소의 갯수를 구하는 문제이다, 우선 입력이 문자열이므로, 문자열을 정수로 치환하는 해싱작업이 필요하다. 해시 함수를 직접 만드는 경우도 있지만, 여기서는 unordered_map을 통해 값 검색을 해주었다. 키는 입력받은 문자열이고, 값(value)은 그 문자열이 입력받은 순서의 번호이다. 두 문자열이 해시에 없으면 삽입하는 작업을 해주고, 다음에 두 문자열의 집합을 병합해준다. 그 후 입력받은 문자열이 속해있는 집합의 개수를 출력하면 된다.

우선 cin으로 문자열을 입력받기 위해 ios_base::sync_with_stdio(false); cin.tie(NULL); 두 구문을 넣어주었다. 그렇지 않으면 시간초과가 난다. 또 위에서 설명했지만, 일반적인 map을 사용할 경우에는 시간초과가 발생한다. 따라서 해시 맵인 unordered_map을 사용하여야 한다.

유니온 파인드에서도 집합의 루트는 음수 값을 가져야 하므로, 그 집합의 크기를 절댓값으로 가지는 음수로 표현하였다. 따라서 집합이 합병될 때마다 서로 다른 두 집합의 크기를 누적해주었다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <memory.h>

using namespace std;

int p[200000];

int find(int n) {
	if (p[n] < 0) return n;
	p[n] = find(p[n]);
	return p[n];
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	p[a] += p[b];
	p[b] = a;
}

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

	int t, n, cnt;
	string in, in2;
	unordered_map<string, int> m;
	cin >> t;
	while (t--) {
		cnt = 0;
		cin >> n;
		memset(p, -1, sizeof(int)* 200000);
		m = unordered_map<string, int>();
		for (int i = 0; i < n; i++) {
			cin >> in >> in2;
			if (m.find(in) == m.end()) {
				m.insert({ in, cnt });
				cnt++;
			}
			if (m.find(in2) == m.end()) {
				m.insert({ in2, cnt });
				cnt++;
			}
			int val = m.find(in)->second;
			merge(m.find(in)->second, m.find(in2)->second);

			cout << -p[find(val)] << '\n';
		}
	}
	return 0;
}