Baekjoon 4195번 친구 네트워크

문제

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

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

struct disjointSet{
    map<string, string> parent;
    map<string, int> rank, size;
    void makeNode(string u){
        if(parent[u] != "") return;
        parent[u] = u;
        rank[u] = 1;
        size[u] = 1;
    }
    string find(string u){
        if(u == parent[u]) return u;
        return parent[u] = find(parent[u]);
    }
    void merge(string u, string v){
        u = find(u); v = find(v);
        if(u == v) return;
        if(rank[u] > rank[v]) swap(u, v);
        parent[u] = v;
        if(rank[u] == rank[v]) rank[v]++;
        size[u] = size[v] = size[u]+size[v];
    }
    int getSize(string u, string v){
        u = find(u); v = find(v);
        if(u == v) return size[u];
        return size[u]+size[v];
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int f;
        cin >> f;
        disjointSet d;
        string a, b;
        for(int i = 0; i < f; i++){
            cin >> a >> b;
            d.makeNode(a);
            d.makeNode(b);
            d.merge(a, b);
            cout << d.getSize(a, b) << "\n";
        }
    }
    return 0;
}

분리 집합(disjoint set); 유니온-파인드(union-find) 자료구조를 응용하여 푸는 문제이다. 입력 원소가 string 자료형이므로 hash map 을 사용하여 disjoint set 을 구현하여야 한다.

예제로 주어진 테스트 케이스 안에서만 생각하다 보니 disjoint set 의 필요성을 떠올리지 못했던 것과, disjoint set 의 find 함수 구현 과정에서 return 을 else 로 작성하는 바람에 아주 많은 시간 삽질을 했다.