Life Engineering
[BOJ 4195] 친구 네트워크 (C++) 본문
https://www.acmicpc.net/problem/4195
#include <vector>
#include <iostream>
#include <map>
using namespace std;
map<string, string> m; //union-find map
map<string, int> cnt; //그룹 원 수 map
string find_(string s){
if (m[s]==s){
return s;
}
return m[s]=find_(m[s]);
}
string union_(string a, string b){
string pa=find_(a);
string pb=find_(b);
if (pa==pb){ //같은 집합 속할 경우
return pb;
}
m[pa]=pb;
cnt[pb]+=cnt[pa]; //부모 쪽으로 자기 그룹원 모두 편입
cnt[pa]=0;
return pb;
}
int main(){
int T;
vector<int> ans;
cin>>T;
while (T--){
m.clear();
cnt.clear();
string a,b;
int F;
cin>>F;
for (int i=0; i<F; i++){
cin>>a>>b;
if (m.find(a)==m.end()){
m[a]=a;
cnt[a]=1;
}
if (m.find(b)==m.end()){
m[b]=b;
cnt[b]=1;
}
string pb=union_(a,b);
ans.push_back(cnt[pb]);
}
}
for (int i=0; i<ans.size(); i++){
cout<<ans[i]<<"\n";
}
return 0;
}
Union-Find 문제
map을 이용해서 각 member와 parents, 각 member와 각 group 원 수를 연결했는데 이렇게 하면 메모리가 많이 소모된다.
다른 분들의 풀이법에 의하면 주로 쓰는 방식은 map 에 key로 이름을 입력받고, value로 index를 해서(입력받을 때마다 이 index는 증가하는 방식으로) 이 index를 기반으로 Union-find 를 수행하는 방식이었다. 이렇게 하면 메모리 소모를 최소화할 수 있다.
친구 관계가 발생할 때 , 처음 들어온 친구면 map에 넣어주고 그룹원은 1로 초기화한다.
그 후 union_ 함수를 실행하여 각 친구의 부모 노드를 찾고, 부모 노드의 그룹원 수에 다른 부모 노드의 그룹원 수를 추가하여 그룹원 수를 편입한다. 그룹원 수를 추가하는 방식이 이 문제를 푸는 포인트라 할 수 있겠다.
두 친구가 같은 그룹인 경우를 빼먹어서 여러번 AC를 받지 못했다.
두 친구가 같은 그룹에 속할 경우에는 그 그룹원 수를 그대로 리턴하고/
같은 그룹이 아닐 경우에는 부모 노드-다른 부모 노드를 서로 연결하고 그룹원 수를 편입하고 그 그룹원 수를 리턴하면 된다.
처음에 복잡하게 생각해서 find 를 여러번 호출해서 시간 초과가 떴다. 다 부모를 최신으로 업데이트 해주고->같은 부모를 가진 애들 세는 방식으로 하다 보니 시간초과가 생겼다.
그러나 "그룹원 수"라는 자료구조를 만든다음(이것 역시 map 말고 Index를 이용해서 배열로 구현해야 메모리 소모를 줄인다) , 합쳐져서 같은 부모를 가지는 경우 그룹원 수를 더해주는 방식을 취하면 모두 해결된다.
'Problem Solving' 카테고리의 다른 글
[BOJ 9466] 텀 프로젝트 (C++) (0) | 2021.08.17 |
---|---|
[BOJ 2887] 행성 터널 (0) | 2021.08.12 |
[BOJ 1976] 여행 가자(C++) (0) | 2021.08.10 |
[BOJ 1261] 알고스팟 (C++) (0) | 2021.08.09 |
[BOJ 9202] Boggle (C++) (0) | 2021.07.22 |