백준 4195 친구 네트워크

문제 링크 : https://www.acmicpc.net/problem/4195

※선행해야 할 알고리즘 : Disjoint-set(Union-Find)

Algorithm : 친구의 이름이 둘씩 입력될 때, 두사람의 친구가 몇 명씩 연결되어 있는지 출력

1. 두 번째 입력 예시를 통해 예를 들어본다면

3

Fred Barney

Betty Wilma

Barney Betty

처음에 Fred Barney가 입력되면 하단과 같이 트리가 연결되고 두 사람의 네트워크는 2가 된다.

두 번째로 Betty Wilma가 입력되면 하단과 같은 새로운 트리가 생겨 두 사람의 네트워크는 2된다.

마지막으로 Barney Betty이 입력이 되는데 Barney Betty는 기존에 입력되어 있던 사람들이기에 트리가 생성되지 않고 Barney Betty가 연결되기만하여 두 사람의 네트워크는 4가 된다.

2. 이 때, 사람의 이름 vector안에서 사람의 이름을 검색해나가며 Union-Find를 실행하면 분명 시간초과가 날 것이다. 따라서 친구가 입력될 때마다 기존에 있는지 검색을 하여 미리 x와 y를 잡아 Union해주는 것이 좋다.

(여러가지 방법이 있겠지만 저는 map을 활용하였고, 이런 알고리즘에서 가장 흔히 쓰이는 템플릿이므로 모르시는 분들은 익혀두시는 것을 추천)

3. Union시에는 x와 y의 값이 다를 때(즉, 네트워크가 연결되어 있을 때) 친구의 수를 누적해서 더해주는 방식으로 진행

4. 1~3을 Disjoint-set 알고리즘을 활용하면 다음과 같다.

//kukliife.tistory.com #include<cstdio> #include<vector> #include<map> using namespace std; int set[200002]; int friend_num[200002]; char Friend1[21], Friend2[21]; int n; int Find(int x) { if (x == set[x]) return x; return set[x] = Find(set[x]); } int Union(int x, int y) { x = Find(x); y = Find(y); if (x != y) { set[x] = y; friend_num[y] += friend_num[x]; friend_num[x] = 1; } return friend_num[y]; } int main() { int T; scanf("%d", &T); for (int c = 0; c < T; c++) { int count=1; map<string, int> friend_set; scanf("%d", &n); for (int i = 1; i <= (2 * n); i++) { set[i] = i; friend_num[i]=1; } for (int i = 0; i < n; i++) { scanf("%s %s", &Friend1, &Friend2); if (friend_set.count(Friend1)==0)//친구집합에 f1이 없으면 friend_set[Friend1] = count++; if (friend_set.count(Friend2)==0) friend_set[Friend2] = count++; printf("%d\n", Union(friend_set[Friend1], friend_set[Friend2])); } } return 0; }