백준 온라인 저지의 4195번 친구 네트워크 문제입니다.
[링크] https://www.acmicpc.net/problem/4195
문제 조건과 설명
어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 단, 입력은 이름(문자)로 주어진다.
친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.
Input
첫째 줄에 테스트 케이스의 개수가 주어진다.
각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어진다.(F < 100,000)
다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다.
친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자나 소문자로만 이루어진 길이 20 이하의 문자열이다.
Output
친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.
생각한 아이디어
Union & Find 설명 - https://chanhuiseok.github.io/posts/improve-7/
기존에 유니온 파인드 자료구조를 설명할 때에는 각 노드의 값을 정수형으로 설정하였습니다.
그러나 이 문제의 경우, 각 노드의 대푯값이 정수가 아니라 문자열(사용자 아이디)인 상황입니다.
우선 맨 처음 인풋값이 들어왔을 때, 유니온-파인드를 수행할 경우 어떻게 되는지 알아보겠습니다.
- Input
1
2
3
Fred Barney
Barney Betty
Betty Wilma
Union & Find 설명 포스팅에 나와있는 대로 union 연산, find 연산 등을 그대로 구현하면 되지만, 이 문제는 노드의 대푯값이 문자열인 것이 다른 점입니다.
위 그림과 같이 두 집합이 합쳐질 때 집합의 사이즈가 더 큰 쪽에 합쳐짐을 알 수 있습니다.
또한 구현상에서 집합의 사이즈는 size 배열에 저장하게 되는데, 대푯값의 size 배열 값에 해당 집합의 size가 저장됩니다.
예를 들어 그림 [3]의 경우, Betty와 Wilma를 합치는데, Betty의 대푯값은 Fred 입니다. 즉, Fred가 대표인 집합의 사이즈는 3이었고, Wilma는 1이었으니 Wilma는 Fred의 집합에 합쳐집니다.
또한, Fred가 대표인 집합의 사이즈는 4로 증가합니다.
다시 말해, 합치기 연산의 대상이었던 Betty나 Wilma의 size가 증가하는 것이 아니라, 대푯값인 “Fred” 의 size 값이 1 증가하게 될 것입니다.
이 점만 유의하여 코드를 그대로 작성하면 됩니다.
또한 대푯값이 문자열이므로, map 자료구조를 활용할 때 해당 문자열이 정수에 대응될 수 있도록 구현하면 됩니다. key 값을 문자열, value 값을 정수로 하고 그 value값을 노드의 값으로 삼으면 될 것입니다.
C++에서 map 자료구조에 어떤 key가 있는지 확인하는 방법은 다양하지만, 그 중에서 count 함수를 사용해서 골라내는 방법이 있습니다.
1
2
3
map<string, int> map;
int cnt = map.count("Fred") // 0 혹은 그 이상의 숫자
// cnt 값이 0이었을 경우, map 자료구조에 없었던 문자열임을 알 수 있음
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
using namespace std;
int sizes[200002];
int link[200002];
int finds(int x) {
if (link[x] == x) return x;
return link[x] = finds(link[x]);
}
void unite(int a, int b) {
a = finds(a);
b = finds(b);
if( a != b ){
if (sizes[a] < sizes[b]) swap(a, b);
sizes[a] += sizes[b];
link[b] = a;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t, F, p1, p2;
cin >> t;
string in1, in2;
for (int T = 0; T < t; T++) {
cin >> F;
// 초기화하기
for (int i = 0; i < 200002; i++) {
sizes[i] = 1;
link[i] = i;
}
map<string, int> map;
int nodeNum = 1;
for (int i = 0; i < F; i++) {
// union
cin >> in1 >> in2;
// map 에 in1이 없었을 경우, 그 map에 노드 번호로 지정
if (map.count(in1) == 0) map[in1] = nodeNum++;
if (map.count(in2) == 0) map[in2] = nodeNum++;
unite(map[in1], map[in2]);
p1 = finds(map[in1]);
p2 = finds(map[in2]);
cout << max(sizes[p1], sizes[p2]) << '\n';
}
}
return 0;
}