[Baekjoon] 4193번: 친구 네트워크 (c++)

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

4195번: 친구 네트워크

 

Union-Find 문제인데, 숫자가 아니라 string 형태이다보니 처음에 어떤식으로 접근해야할지 감이 잘 안잡혔다.

내가 사용한 방법은 각각 친구관계는 net에 저장하고, net과 관련되어있는 친구네트워크의 크기(길이)는 cnt에 저장해서, 주어진 입력 a, b 둘중 cnt크기가 더 큰곳에 작은것을 합쳐주는 방식으로 진행했다.

 

1. net 해시맵에 입력받은 문자열을 자기자신으로 초기화하고, cnt값도 1으로 함께 초기화

2. Union으로 a값의 부모를 찾고, b값의 부모를 찾아서 a와 b 둘중 cnt사이즈가 더 큰곳에 작은것을 합침

    - 이때, 만약 Union함수에서 a의 부모와 b의 부모가 같다면, 연산을 할 필요가 없으므로 return

ex) 예시가 
1
1
a b
b c
c a

인 경우, a - b - c  이런식으로 연결되어있기 때문에, 5번째줄 c a가 들어왔을 때, c의 부모는 a이므로 [a] = a 이런식으로 되어버리기 때문에, a와 b의 부모가 같을 경우에는 return을 해줘야 한다.

3. 주어진 입력 a의 부모를 찾아 a_parent에 저장, b의 부모도 b_parent에 저장

4. a_parent의 네트워크 크기(cnt[a_parent])와 b_parent 네트워크 크기(cnt[b_parent])를 비교해서 더 큰값 출력

---

코드(c++)

#include <string>
#include <vector>
#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;

unordered_map<string, string> net;
unordered_map<string, int> cnt;

string Find(string x){
    if(x == net[x]) return x;
    
    string p = Find(net[x]);
    net[x] = p;
    return p;
}
void Union(string a,string b){
    a = Find(a);
    b = Find(b);
    
    if(a == b) return;
    else if(cnt[a] > cnt[b]) { net[b] = a; cnt[a]+=cnt[b]; }
    else { net[a] = b; cnt[b]+=cnt[a]; }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   
    int t, F;
    string a,b;
    
    cin >> t;
    while (t--) {
        cin >> F;
        net.clear();
        cnt.clear();
        for(int i=0;i<F;i++){
            cin >> a >> b;
            
            if(net.count(a) == 0){net[a] = a; cnt[a] = 1;}
            if(net.count(b) == 0){net[b] = b; cnt[b] = 1;}
            
            Union(a, b);
            
            string a_parent = Find(a);
            string b_parent = Find(b);
            
            cout << max(cnt[a_parent], cnt[b_parent]) << "\n";
            
        }
    }
   
    return 0;
}