[백준/Baekjoon] 4195 친구 네트워크 C++ :: Union find & Data structure

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

4195번: 친구 네트워크

---

1. Logic

unordered_map을 사용해서 이름을 저장해준다. union find알고리즘을 사용하기 위해서 몇번째 노드인지 같이 넣어줬다. 즉 key값은 이름 value값은 고유 번호이다.

 

노드의 부모를 찾아서 merge해 줄 때 부모 노드의 친구 수를 더해주면 된다. 주의해야 할 점은 사람1의 부모와 사람2의 부모가 같을 경우 2번 더해주는 상황이 일어나기 때문에 더하지 않도록 처리를 해줘야 한다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

unordered_map<string, int> um;

int node[200001];
int friendNum[200001];

int find(int x) {
    if(node[x] == x) return x;
    
    return node[x] = find(node[x]);
}

void merge(int n1, int n2) {
    int x = find(n1);
    int y = find(n2);
    
    if(x == y) return;
    
    if(x < y) {
        node[y] = x;
        friendNum[x] += friendNum[y];
    }
    else {
        node[x] = y;
        friendNum[y] += friendNum[x];
    }

}

int main() {
    ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
    int t;
    cin >> t;
    
    while(t--) {
        um.clear();
        for(int i = 1; i <= 200001; i++) {
            node[i] = i;
            friendNum[i] = 1;
        }
        
        int n;
        cin >> n;
        
        int number = 1;
        for(int i = 0; i < n; i++) {
            string name1, name2;
            cin >> name1 >> name2;
            
            if(!um[name1]){
                um[name1] = number;
                number++;
            }
            if(!um[name2]){
                um[name2] = number;
                number++;
            }
            
            int a = um[name1];
            int b = um[name2];
            
            merge(a, b);
            int root = find(a);
            cout << friendNum[root] << '\n';
        }
    }
}

 

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90