[백준]4195번 친구 네트워크 - C/C++ - STL 사용 X

https://www.acmicpc.net/problem/4195

4195번: 친구 네트워크

문제

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

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

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

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

출력

친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

---

Union - Find와 해시를 통해 풀 수 있는 문제이다. 다만 이름의 길이가 20승인데 소문자와 대문자 모두 가능하므로 충돌이 절대 나지 않기 위해서는 52^21 보다 큰 해시 맵이 필요하기 때문에 충돌을 방지해야 한다. 충돌을 방지하기 위해 Linked List로 해시 맵을 구현하였다.

#include <iostream>
#include <string>
using namespace std;

#define HASH_SIZE (200010)
#define MOD (200010 - 1)
struct Node {
	Node* next;
	int idx;
	char* name;
}nodearr[HASH_SIZE];

int N, M;
int node_cnt = 0;
Node* get_node(char name[], int idx) {
	Node* node = &nodearr[node_cnt++];
	node->name = name;
	node->idx = idx;
	return node;
}

int make_hash(char s[]) {
	long long ret = 0;
	for (register int i = 0; s[i] != 0; i++) {
		ret *= 33; ret += (s[i]-'A' + 1);
	}
	return (int)(ret & MOD);
}

Node* h[HASH_SIZE];
int get(char name[]) {
	int hash = make_hash(name);
	Node* cur = h[hash];
	while (cur != nullptr) {
		bool flag = true;
		for (int i = 0; i < 21; i++) {
			if (name[i] != cur->name[i]) { flag = false; break; }
		}
		if (flag) return cur->idx;
		cur = cur->next;
	}
}

void put(char name[], int idx) {
	int hash = make_hash(name);
	Node* node = get_node(name,idx);
	if (h[hash] == nullptr) h[hash] = node;
	else {
		node->next = h[hash];
		h[hash] = node;
	}
}

int contain(char name[]) {
	int hash = make_hash(name);
	if (h[hash] == nullptr) return 0;
	else {
		Node* cur = h[hash];
		while (cur != nullptr) {
			bool flag = true;
			for (int i = 0; i < 21; i++) {
				if (name[i] != cur->name[i]) { flag = false; break; }
			}
			if (flag) return 1;
			cur = cur->next;
		}
		return 0;
	}
}


struct node {
	int parent;
	int num = 1;
}dset[HASH_SIZE];


int Find(int a) {
	if (dset[a].parent == a)
		return a;
	return dset[a].parent = Find(dset[a].parent);
}

int Union(int x, int y) {
	int a = Find(x), b = Find(y);
	if (a != b) {
		dset[b].parent = dset[a].parent;
		dset[a].num += dset[b].num;
	}
	return dset[a].num;
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> N;

	int key1, key2;
	int x, y;
	int name_cnt = 1;
	while (N--) {
		for (int i = 0; i < HASH_SIZE; i++) {
			dset[i].parent = i;
			dset[i].num = 1;
		}
		cin >> M;
		while (M--) {
			char* n1 = (char*)malloc(sizeof(char) * 21);
			char* n2 = (char*)malloc(sizeof(char) * 21);
			//char n1[21]; char n2[21];
			cin >> n1 >> n2;
			if (!contain(n1)) { put(n1, name_cnt++); }
			if (!contain(n2)) { put(n2, name_cnt++); }
			cout << Union(get(n1), get(n2)) << "\n";

		}

	}

}

---

어제 SWEA 해설 특강에서 배운 해시와 다시 공부하려고 했던 Union Find 가 결합된 문제여서 풀게 되었다. Map 을 쓰기보단 STL 없이 구현해보고 싶어서 해시 맵을 직접 구현해보았으나 SWEA 문제와는 다르게 대소문자가 모두 가능하였고 문자열의 길이도 20이었기 때문에 어제 쓰지 않았던 충돌을 방지해야 했다. 그래서 구글링을 해서 해시 맵을 linked list로 이어주는 방법을 알게 되었다. 하지만 여기서 의문인 점은 위 코드에서 char 배열을 malloc 해주면 잘 작동하는데 그냥 char [21] 하게 되면 풀리지를 않았다. 이 부분이 참 의문이다..