문제 출처
문제
민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.
어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.
친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.
출력
친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.
테스트 케이스
2
3
Fred Barney
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty
answer:
2
3
4
2
2
4
알고리즘 분류
UnionFind
풀이
전역변수로 unionfind 자료구조를 만들기 위해 parent 배열, 그리고 친구 네트워크에 몇 명이 있는지 저장할 nfriend 배열을 선언해 줍니다. 이미 입력받은 친구인지 아닌지 확인하기 위해 map을 선언해 줍니다.
함수부터 설명하겠습니다. getParent는 매개변수 x의 부모를 찾아주는 함수입니다. parent[x]에 기록된 숫자가 x와 같다면 자기 자신이 부모이므로 함수를 종료해주고 아니라면 재귀를 통해 부모를 찾아서 반환해 줍니다.
unionFind는 a와 b의 부모를 찾고 기준을 정해(큰 숫자가 부모 or 작은 숫자가 부모) 두 집합을 합쳐 줍니다. nfriend는 the number of the friend 입니다. if(a > b)인 경우 부모가 b인 경우 기존 값에서 nfriend[a]을 더해 친구 관계에 있는 친구의 수를 저장해 줍니다.
int parent[200001];
int nfriend[200001];
map<string, int> m;
int getParent(int x) {
if (parent[x] == x) return x;
return parent[x] = getParent(parent[x]);
}
void unionParent(int a, int b) {
a = getParent(a);
b = getParent(b);
if (a > b)
{
parent[a] = b;
nfriend[b] += nfriend[a];
}
else if (a < b)
{
parent[b] = a;
nfriend[a] += nfriend[b];
}
}main 부분입니다. test case 개수인 T와 처음부터 현재까지 입력받은 친구의 수를 저장할 count를 선언해 줍니다. 그리고 find 함수를 사용하기 위해 map 자료구조의 iterator를 선언해 줍니다.
첫 번째 반복문 안으로 들어가보면 우선 test case마다 친구 네트워크의 수를 각각 구해야 하므로 map을 초기화하고 count도 초기화합니다. 그리고 parent 배열은 i로 nfriend 배열은 1로 각각 초기화합니다. string str1과 string str2를 선언하고 unionParent하기 위해 int a와 b를 선언해 줍니다.
두 번째 반복문 안으로 들어가면 str1이 map에 있는지 확인하고 그 iterator를 it에 저장해 줍니다. 만약 it == m.end()라면(str1이 없다면) m[str1(key)], count(value)로 map에 저장해 줍니다.(map을 사용하는 이유는 시간복잡도가 logN으로 효율적이기 때문입니다.) else의 경우 str1이 존재하므로 str1의 value값을 a에 저장해 줍니다. (str1과 str2 -> a와 b) unionParent를 통해 union해주고 getParent를 통해 root를 찾아서 nfriend[root](친구 네트워크의 수)를 출력해 줍니다.
int T, count;
map<string, int> ::iterator it;
cin >> T;
for (int i = 0; i < T; i++)
{
m.clear();
count = 0;
for (int i = 0; i < 200001; i++) {
parent[i] = i;
nfriend[i] = 1;
}
string str1, str2;
int F, a, b;
cin >> F;
for (int j = 0; j < F; j++)
{
cin >> str1 >> str2;
it = m.find(str1);
if (it == m.end()) {
m[str1] = ++count;
a = count;
}
else
a = it->second;
it = m.find(str2);
if (it == m.end()) {
m[str2] = ++count;
b = count;
}
else b = it->second;
unionParent(a, b);
int root = getParent(a);
cout << nfriend[root] << '\n';
}
}
}전체 코드
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<string>
using namespace std;
int parent[200001];
int nfriend[200001];
map<string, int> m;
int getParent(int x) {
if (parent[x] == x) return x;
return parent[x] = getParent(parent[x]);
}
void unionParent(int a, int b) {
a = getParent(a);
b = getParent(b);
if (a > b)
{
parent[a] = b;
nfriend[b] += nfriend[a];
}
else if (a < b)
{
parent[b] = a;
nfriend[a] += nfriend[b];
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T, count;
map<string, int> ::iterator it;
cin >> T;
for (int i = 0; i < T; i++)
{
m.clear();
count = 0;
for (int i = 0; i < 200001; i++) {
parent[i] = i;
nfriend[i] = 1;
}
string str1, str2;
int F, a, b;
cin >> F;
for (int j = 0; j < F; j++)
{
cin >> str1 >> str2;
it = m.find(str1);
if (it == m.end()) {
m[str1] = ++count;
a = count;
}
else
a = it->second;
it = m.find(str2);
if (it == m.end()) {
m[str2] = ++count;
b = count;
}
else b = it->second;
unionParent(a, b);
int root = getParent(a);
cout << nfriend[root] << '\n';
}
}
return 0;
}