[C++] 4195번 친구 네트워크 - 자료 구조, 해시를 사용한 집합과 맵, 분리 집합

1. 문제

• 두 사람의 친구 네트워크에 몇 명 있는지 구하는 프로그램을 작성하시오.

<입력>

• - 1 -   테스트 케이스의 개수 \(T(1 \leq T \leq 100,000)\)
• - F개의 줄 -   친구 관계가 생긴 순서대로 주어짐. 친구 관계는 두 사용자의 아이디로 이루어져 있으며 이는 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

<출력>

• 친구 관계가 생길 때마다 두 사람의 친구 네트워크에 몇 명이 있는지 구하시오.

2. 재정의

• 집합의 원소 개수 구하기

3. 해결 방법

• unordered-map에 헤시를 써서~~

4. 실수한 점, 개선할 점

• MAX_F가 아니라 MAX_F*2개 만큼 배열을 잡아야 한다. 그 이유는 F개의 친구 관계가 나오므로 최대 친구의 수는 2*F이기 때문이다.

 

<코드>

#include <iostream>
#include <string.h>
#include <vector>
#include <unordered_map>

using namespace std;

const int MAX_F = 100001;

// <문제>
// 테스트 캐이스의 수 T, 친구 관계의 수 F
int T, F;

// <Union find>
// string idx를 int idx로 변환
unordered_map<string, int> hashmap;
// node의 index
int idx;

// 루트 노드 root[], 노드의 차수 node_rank[]
int root[2 * MAX_F], node_rank[2 * MAX_F];
// 한 집합에서 노드의 개수
int nodeCount[2 * MAX_F];

void input() {
    cin >> F;
    // 초기화
    for(int i=0; i<2 * MAX_F; i++) {
        root[i] = i;
        node_rank[i] = 0;
        nodeCount[i] = 1;
    }
    hashmap.clear();
    idx = 0;
}

int find(int x) {
    if(x == root[x])
        return x;
    else
        // find연산 최적화
        return root[x] = find(root[x]);
}

int Union(int x, int y) {
    x = find(x), y = find(y);
    
    // 두 값의 root가 같으면 합치지 않기
    if(x == y)
        return nodeCount[x];
    
    // Union-by-rank 최적화
    // 항상 높이가 더 낮은 트리를 높이가 높은 트리 밑에 넣는다.
    if(node_rank[x] < node_rank[y]) {
        root[x] = y;
        nodeCount[y] += nodeCount[x];
        
        return nodeCount[y];
    }
    else {
        root[y] = x;
        nodeCount[x] += nodeCount[y];
        // 만약 트리의 높이가 같다면 합친 후 x의 높이 +1
        if(node_rank[x] == node_rank[y])
            node_rank[x]++;
        
        return nodeCount[x];
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> T;
    while(T--) {
        input();
        for(int i=0; i<F; i++) {
            string s1, s2;
            cin >> s1 >> s2;
            
            // 아직 해시맵에 등록되지 않았을 경우 idx 만들어주기
            if(!hashmap.count(s1))
                hashmap[s1] = idx++;
            if(!hashmap.count(s2))
                hashmap[s2] = idx++;
            
            //cout << hashmap[s1] << ' ' << hashmap[s2] << '\n';
            
            cout << Union(hashmap[s1], hashmap[s2]) << '\n';
        }
    }
    
    return 0;
}

 

<Union-find 알고리즘>

https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

[알고리즘] Union-Find 알고리즘 - Heee's Development Blog

 

<unordered_map>

https://math-coding.tistory.com/31

[Data Structure] unordered_map 사용법

 

<코드 바로가기>

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

4195번: 친구 네트워크

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.