[백준 4195 C++][G2] 친구 네트워크

⭐️난이도

Gold 2

---

⭐️문제

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

4195번: 친구 네트워크

 

---

⭐️ Idea Flow 

먼저 문제를 해석해보면 친구 관계는 모두 이어져있는 것이 아니라 여러 개의 친구 관계로 이루어져 있을 가능성이 높다.

이 때 바로 생각난 것이 바로 Disjoint Set(서로소 집합)이다. Union-Find 방식을 이용하면 될 것이라고 생각했다.

그리고 Disjoint set를 사용하려면 각 이용자에게 index를 부여해야 한다.

하지만 id의 입력 자체를 string(문자열)로 받으니 pair 방식으로 id(string)와 index(int)를 묶어줘야 겠다고 생각했다.

 

그래서 생각한 자료구조가 바로 unordered_map이다.

unordered_map은 map과 거의 유사하지만, hash table 기반으로 map과는 다르게 key를 sort하지 않는다.

또한 hash table 기반이므로 탐색에 걸리는 시간이 O(1)이다.

 

unordered_map<string, int> hashmap을 선언한 이후, ID 2개를 받으면서 hashmap에 해당 key에 value가 있는지 확인을 한다.

만약 이전에 입력받은 ID가 있다면 index 값이 value 값으로 들어가 있을 것이며, 만약 그렇지 않으면 value가 존재하지 않을 것이다. ( .count() 이용)

이후 id_1와 id_2에 해당하는 인덱스를 변수에 각각 저장한 후, unionParent를 통해 parent 값을 합쳐준다.

 

그렇다면 친구 관계로 이어진 친구의 수는 어떻게 확인할까?

Disjoint set을 이용하면 더 수월하게 저장이 가능 할 것이다. unionParent 함수를 통해 index가 더 작은 쪽으로 값을 합쳐준다.

 

그렇다면 friend_num이라는 int형 vector를 선언 한 후에, 초기 값을 모두 1로 설정한다. (자신만으로 친구 수가 1명)

unionParent 함수에서 parent를 통합할 때에 "index가 더 큰 쪽의 친구 수"를 "index가 더 작은 쪽의 친구 수"에 더해준다.

 

void unionParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);

    // 수가 더 큰 쪽에 있는 친구의 수를, 수가 더 작은 쪽에 더한다
    if (a < b) {
        parent[b] = a;
        friend_num[a] += friend_num[b];
    }
    else if(a>b){
        parent[a] = b;
        friend_num[b] += friend_num[a];
    }
}

 

 

---

⭐️Code

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_map>

using namespace std;

// 4195 - 친구 네트워크
unordered_map<string, int> hashmap; // first: id, second: index
vector<int> parent, friend_num; // disjoint-set을 위한 배열, 연결된 친구가 몇 명인지 저장하는 변수


int getParent(int x) {
    if (parent[x] == x) return x;
    return parent[x] = getParent(parent[x]);
}

void unionParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    
    // 수가 더 큰 쪽에 있는 친구의 수를, 수가 더 작은 쪽에 더한다
    if (a < b) {
        parent[b] = a;
        friend_num[a] += friend_num[b];
    }
    else if(a>b){
        parent[a] = b;
        friend_num[b] += friend_num[a];
    }
}

void initParent(int num){
    // 한 관계에 두 개의 id가 주어지기 때문에
    // 최대 사람 수는 (관계의 수) * 2 이다.
    parent.assign(num * 2 + 1, 0);
    friend_num.assign(num * 2 + 1, 1);

    for (int i = 0; i <= num * 2; i++) {
        parent[i] = i;
    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int testcase;

    cin >> testcase;
    while(testcase--){
        hashmap.clear();
        int idx = 0, f = 0;

        cin >> f;
        initParent(f);

        // id_1의 인덱스 번호, id_2의 인덱스 번호
        int friend_n1 = 0, friend_n2 = 0;

        for (int i = 0; i < f; i++) {
            string id_1, id_2;
            cin >> id_1 >> id_2;

            // key id_1에 해당하는 value의 개수가 없을 때
            if (hashmap.count(id_1) == 0) {
                hashmap[id_1] = ++idx;
                friend_n1 = idx;
            }
            else { // 이미 존재한다면 key에 해당하는 value를 가지고 온다
                friend_n1 = hashmap[id_1];
            }

            if (hashmap.count(id_2) == 0) {
                hashmap[id_2] = ++idx;
                friend_n2 = idx;
            }
            else {
                friend_n2 = hashmap[id_2];
            }

            // unionParent를 통해 부모를 합친다.
            unionParent(friend_n1, friend_n2);
            int target = getParent(friend_n1);
            cout << friend_num[target] << '\n';
        }
    }

    return 0;
}

 

---

⭐️ Feedback

leet code를 하면서 unordered_map (hash table)이 생각보다 많은 상황에서 쓰일 수 있다는 것을 알게 되었다.

이번에는 문제를 보고 분류나 힌트를 전혀 보지 않고 혼자서 풀이를 만들었다.

그리고 난 이후에 다른 사람의 풀이를 보니 거의 똑같아서 너무너무 신기하고 뿌듯하다.

물론 첫 시도에는 시간 초과가 나서 이후에 방식을 바꾸긴 했지만, 이 정도면 발전하고 있는 것 같다.

 

vector, queue, stack, string 외의 다른 STL은 거의 쓰지 않고, 어떤 때에 써야할지 전혀 감이 오지 않았는데,

다른 사람의 코드를 분석해보니 천천히 감이 잡히는 것 같다.