[BOJ] 4195 : 친구 네트워크
💉문제 내용
💉입출력
🧺입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.
🧺출력
친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.
🔋예제 입출력
🔮예제 입력
2
3
Fred Barney
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty
🔮예제 출력
2
3
4
2
2
4
💉문제 분석
🔋분류
분리집합, 해쉬
🔋난이도
골드II
💉문제 풀이
🔋해법
🧺입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.
🧺출력
친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.
🔮예제 입력
2
3
Fred Barney
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty
🔮예제 출력
2
3
4
2
2
4
🔋분류
분리집합, 해쉬
🔋난이도
골드II
💉문제 풀이
🔋해법
이 문제는 해쉬랑 분리집합을 섞은문제입니다.
해법은 간단합니다.
입력으로 들어오는 친구들중에서 알려진친구가 아니면, 그 친구이름으로 숫자가 들어갑니다.
이 숫자는 매번 1씩증가하며, 알려진 친구라면 그냥 그대로 쭉 갑니다.
어차피 다음에가서 [] 연산자로 해당 key에맞는 value를 찾으면 되니까요.
모든 정보를 갱신했다면, 두 집합을 합쳐줍니다.
그다음 결과값은 각각 가지고있는 친구들의 수가 적혀진 배열의 입력한 a또는 b의 부모노드번째인덱스가 됩니다.
🔋소스코드
#include <bits/stdc++.h>
constexpr int MAX = 1000000;
int parent[MAX], fcount[MAX];
int getParent(int value) {
if (parent[value] == value) return value;
return parent[value] = getParent(parent[value]);
}
void Union(int a, int b) {
int xa = getParent(a);
int xb = getParent(b);
if (xa < xb) {
parent[xb] = xa;
fcount[xa] += fcount[xb];
}
else if (xb < xa) {
parent[xa] = xb;
fcount[xb] += fcount[xa];
}
}
int main() {
std::ios_base::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
int T, M;
std::cin >> T;
for (int k = 0; k < T; ++k) {
int count = 0;
std::map<std::string, int> m;
std::cin >> M;
for (int i = 0; i < MAX; ++i) {
parent[i] = i;
fcount[i] = 1;
}
for (int j = 0; j < M; ++j) {
int sa, sb;
std::string a, b;
std::cin >> a >> b;
auto it1 = m.find(a);
//만약 알려지지않은 친구라면
if (it1 == m.end()) m[a] = count++;
auto it2 = m.find(b);
//만약 알려지지않은 친구라면
if (it2 == m.end()) m[b] = count++;
Union(m[a], m[b]);
std::cout << fcount[getParent(m[a])] << '\n';
}
}
}
최근에 대회준비때문에 저가 좋아하는 최대유량이나 bfs문제도 풀고있지만,
안풀던 분리집합문제를 풀고있습니다.
분리집합문제는 그래프문제에 비해서 상대적으로 적게 풀었기때문에,
이번에 세그먼트, 구간합문제랑 같이 많이 풀어봐야겠습니다.
💉마치며...
사실 저가 예전에도 언급한 적이있지만,
프로그래밍자체를 시작한건 1년전이지만,
백준문제를 본격적으로 시작한건, 2~3주전입니다.
예전에는 네트워크나 윈도우 프로그래밍같은걸로 삽질 5지게하다가 알고리즘으로 넘어왔습니다.
알고리즘문제를 본격적으로 풀기시작한건 얼마안됬지만,
이번에 대회에서 예선까지라도 통과하고오겠습니다. 화이팅!
(조금만 더 풀면 골드다!!!! 화이팅~~~!!!!)
살짝 tmi지만, 어제 밤새고 엄청 졸린기분으로 아침에 코로나주사맞고왔는데도 3~4시간 쪽잠자고 알고리즘공부....
궁금한 부분있으시면 댓글로 질문주세요~
Author And Source
이 문제에 관하여([BOJ] 4195 : 친구 네트워크), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dpmawile/boj4195저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)