[C++] 백준 4195 친구네트워크

문제 링크

---

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

4195번: 친구 네트워크

접근 방법

---

 문제에서 요구하는 것을 간단히 정리하자면, A라는 인물과 B라는 인물이 친구 관계를 맺었을 때 A의 친구 수와 B의 친구 수를 더하면 된다. 문제를 읽었을 때 두 집합이 연결(친구 관계) 또는 합(친구의 수)하여 진다는 점에 있어서 유니온 파인드 알고리즘이라는 느낌이 확실히 와 닿는다.

 

 유니온 파인드는 크게 자신의 루트를 찾는 find함수와, 두 집한간의 연결을 하는 Union함수를 사용한다.

혹여나 두 함수를 이해하지 못했다면 기본적인 UnionFind 알고리즘을 다시 공부하고 풀어보자.

 

 사실 UnionFind의 구현은 어렵지 않으나, 이 문제는 노드 번호를 이름(문자열)으로 주어지기 때문에 조금 까다롭게 느껴질 수 있다.

 

1. 문자열을 노드 번호로 정리해 보자

map <string, int> name;

name을 map의 자료형으로 위와 같이 정의했을 때, 아래와 같이 처리할 수 있다.

int idx = 1;
for (int j = 0; j < F; j++) {
	string name1, name2;
	cin >> name1 >> name2;
	if (name.count(name1) == 0) 
		name[name1] = idx++;
	if (name.count(name2) == 0) 
		name[name2] = idx++;
	Union(name[name1], name[name2]);
}

문제를 쉽게 해결하기 위해 이름(문자열)에 대해 번호를 매겨주자. 

 지금까지 입력받은 적이 없는 이름이라면 ( if (name.count(name1)==0) ), 번호를 부여한다( name[name1] = idx++) .

즉 idx는 이름에 대한 번호이며, 입력을 받은적이 있는 이름이라면 이미 번호가 매겨져 있다는 뜻으로 무시해도 된다는 것이다.

 

 예를 들면

Fred, Bob -> 1, 2

Jason, Bob -> 3, 2

이렇게 처리가 된다. 

 

이제 어려울 것이 없다. 친구 수는 (cnt[i] = 친구수 (i는 노드 번호) )라는 배열에 저장하며 처리를 할 것이며 Union함수에서 name1과 name2의 친구 관계를 형성함과 동시에 친구수를 더할 것이다.

void Union(int a, int b) {
	a = find(a);
	b = find(b);
	if(a != b)            //이미 친구 관계라면, 친구 수를 합하면 안됨
		cnt[a] += cnt[b]; //친구수의 합
	tree[b] = a;          //친구관계 형성
	cout << cnt[a] << "\n";
}

소스 코드

---

#include <iostream>
#include <map>
#include <string>
#include <cstring>
#include <stdio.h>

using namespace std;
int tree[100010];
int cnt[100010];

int find(int a) { 
	if (tree[a] == -1 || tree[a] == a)  
		return a;
	int root = find(tree[a]);
	return tree[a] = root;
}

void Union(int a, int b) { 
	a = find(a);
	b = find(b);
	if(a != b)              //친구 관계가 아닐 때
		cnt[a] += cnt[b];   //친구 수 합
	tree[b] = a;            //관계를 형성
	cout << cnt[a] << "\n";
}

int main() {

	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
	int T , F;
	cin >> T;

	for (int i = 0; i < T; i++) {
		cin >> F;
		map <string, int> name;
		memset(tree, -1, sizeof(tree));
		fill_n(cnt, 100010, 1);
		int idx = 1;
		for (int j = 0; j < F; j++) {
			string name1, name2;
			cin >> name1 >> name2;
			if (name.count(name1) == 0) 
				name[name1] = idx++;
			if (name.count(name2) == 0) 
				name[name2] = idx++;
			Union(name[name1], name[name2]);
		}
	}
}

개발 환경 : VS2019

질문, 지적 환영합니다!