[BOJ 4195] 친구 네트워크 (C++)

https://www.acmicpc.net/problem/4195

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를 이용해서 배열로 구현해야 메모리 소모를 줄인다) , 합쳐져서 같은 부모를 가지는 경우 그룹원 수를 더해주는 방식을 취하면 모두 해결된다.