BOJ 4195 친구 네트워크 C++

BOJ 4195 친구 네트워크
간결하게 풀어봤다.

🔍 캐치해야할 포인트

1. 테스트케이스가 여러 개 주어지는 문제이다.
   변수와 자료구조들 초기화가 중요하다. 재할당 및 초기화 코드는 먼저 박아놓고 시작하자.

2. '친구 관계가 주어진다' 는 두 사람의 관계가 양방향이다라고 해석할 수 있다. 즉, 무향 그래프라고 생각할 수 있다. (따라서 SSC 풀이도 가능해 보임)

혹은 '관계가 주어진다' 를 집합으로 생각한다면 분리 집합을 떠올리는 것은 그리 어렵지 않다.

3. 분리 집합 풀이까지 떠올렸다면, 일반적인 경우와 달리 노드가 정수가 아닌 문자열로 주어지므로 이 부분을 어떻게 처리할지만 생각하면된다.

---

📙 문자열 Hashing

입력으로 주어지는 이름 문자열들을 분리 집합에서 사용할 parent 배열의 인덱스로 사용하기 위해서는 문자열-숫자 간의 맵핑이 필요하다.

map을 사용한다면 간단하게 구현이 가능하다.

SQL의 auto-increment 처럼 정수형 변수 하나를 선언해두고 1씩 늘려가면서 아직 맵핑이 안되었다면 맵핑, 맵핑이 이미 되었다면 그 값을 사용하게 하면된다.

---

📘 Union-Find 응용 코드 적용

보통은 분리 집합 구현할 때, parent 배열에는 자신의 부모 노드 번호만을 저장한다.

하지만 여기서 한 단계 더 나아가 부모 노드의 번호를 넣되, 최상위 노드에는 음수로 집합의 노드 수를 저장할 수 있다.

int find(int x) {
	if (parent[x] < 0) return x; // 최상위 노드만 음수로 집합의 크기를 갖고 있음.

	return parent[x] = find(parent[x]);

}

int Union(int a, int b) {
	a = find(a);
	b = find(b);

	if (a != b) {
		parent[a] += parent[b]; // 한쪽에는 기존 최상위 노드의 값끼리 더해줘서 union된 집합 크기를 저장.
		parent[b] = a; // 나머지 한 쪽 노드는 다른 노드 자식으로 편입
	}

	return -parent[a];
}

---

📒 코드

#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <vector>

using namespace std;
map<string, int> keyGen;
vector<int> parent;

// Union-Find 알고리즘의 find 함수
int find(int x) {
	if (parent[x] < 0) return x;

	return parent[x] = find(parent[x]);

}

// Union-Find 알고리즘의 union 함수
int Union(int a, int b) {
	a = find(a);
	b = find(b);

	if (a != b) {
		parent[a] += parent[b];
		parent[b] = a;
	}

	return -parent[a];
}

void solution() {
	int T;
	string tmp[2];
	cin >> T;

	while (T--) {
		int F, key = 0;
		parent.assign(200001, -1);
		keyGen.clear();
		cin >> F;

		for (int i = 0; i < F; i++) {
			for (int i = 0; i < 2; i++) {
				cin >> tmp[i];
				if (keyGen[tmp[i]] == 0) keyGen[tmp[i]] = ++key;
			}

			cout << Union(keyGen[tmp[0]], keyGen[tmp[1]]) << '\n';
		}
	}
}

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

---

📚 마치며

출처 : 내 머리