[백준 4195] 친구 네트워크

 

 

 분리 집합과 해시를 이용하는 자료구조 활용 문제다. 문제를 유심히 읽어보면 알 수 있듯이, 친구 집합이 계속해서 합쳐져야 하고 특정 아이디의 유저가 속한 친구 집합을 빠르게 조회할 수 있어야 한다. 따라서 분리 집합을 활용해 이를 효율적으로 처리할 수 있다.

 다만 유저에 대한 정보를 문자열 형태의 아이디로 제공하고 있으므로, 이를 Union-Find 연산 내에서 매번 문자열 형태로 비교하면 효율성이 떨어진다. 나는 그래서 해시 맵을(C++ 내의 unordered_map을 사용했다) 활용해, 각 유저의 아이디에 대한 고유 정수 id값을 부여했다. 이렇게 하면 처음 유저 아이디를 입력받았을 때만, 한 번 id 값을 조회하고 그 이후부터는 정수 id로 빠르게 Union-Find 연산을 처리할 수 있다.

 

 나머지는 일반적인 분리 집합의 구현과 비슷한데, 문제에서는 친구 네트워크에 속한 총인원을 계속 요구하므로 이를 담을 수 있는 배열도 추가적으로 생성한다.

 그리고 어떤 유저가 처음 추가되었을 때, 총 인원 배열의 해당 유저 id 인덱스를 1로 초기화해서 사용한다. 이후 Union 과정에서 만약 병합이 발생한다면, 합쳐질 집합의 root에 저장된 인원수를 합쳐지는 집합의 root의 인원수에 더해주면 된다. 그렇지 않고 이미 두 원소가 같은 집합 내에 속해있다면, 해당 집합의 root가 가지고 있는 인원수를 바로 출력해 준다.

 

 좋아하는 형태의 문제라서 풀이법이 쉽게 떠올랐던 것 같다.

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

unordered_map<string, int> ids;
vector<int> roots;
vector<int> friendNum;

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

    return roots[x] = find(roots[x]);
}

int makeUnion(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);

    if(rootX == rootY) {
        return friendNum[rootX];
    } else if(rootX < rootY) {
        roots[rootY] = rootX;
        friendNum[rootX] += friendNum[rootY];
        return friendNum[rootX];
    } else {
        roots[rootX] = rootY;
        friendNum[rootY] += friendNum[rootX];
        return friendNum[rootY];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t, f;
    string name1, name2;

    cin >> t;

    while(t--) {
        cin >> f;
        ids.clear();
        roots.clear();
        friendNum.clear();

        while(f--) {
            cin >> name1 >> name2;

            if(ids.find(name1)==ids.end()) {
                int id = ids.size();
                ids[name1] = id;
                friendNum.push_back(1);
                roots.push_back(id);
            }
            if(ids.find(name2)==ids.end()) {
                int id = ids.size();
                ids[name2] = id;
                friendNum.push_back(1);
                roots.push_back(id);
            }

            cout << makeUnion(ids[name1], ids[name2]) << "\n";
        }
    }
}