문제

문제 링크

문제 접근

  • 이 문제는 두개의 친구 그룹이 하나로 더해질 때의 인원수를 세는 문제이다.
  • 이 문제는 Union-Find로 접근이 가능하다.
  • 두 친구의 그룹이 Union할 때 각 group의 수를 더해서 출력해주면 된다.
  • 여기서 주의할 점은 두 친구의 parent가 같은 원소라면 Union하지 않는다.
  • 이름이 string 값으로 주어지게 되는데 이름을 map을 이용해서 숫자로 표현할 수 있다면 훨씬 효율적으로 문제를 해결할 수 있다.

코드

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <cstdio>

using namespace std;


int k, n;
string f1, f2;
map<string, int> name;
int par[100020], cnt[100020];

int find(int root){
    if(!par[root])return root;
    return find(par[root]);
}
void Union(int v1, int v2){
    int p1 = find(v1), p2 = find(v2);
    if(p1 != p2) {
        cnt[p1] += cnt[p2];
        par[p2] = p1;
    }
    printf("%d\n", cnt[p1]);
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin >> k;
    while(k--){
        int num = 1;
        cin >> n;
        for(int i = 0; i < n + 2; i++)par[i] = 0, cnt[i] = 1;
        while(n--){
            cin >> f1 >> f2;
            if(name.find(f1) == name.end())name.insert(make_pair(f1, num++));
            if(name.find(f2) == name.end())name.insert(make_pair(f2, num++));
            Union(name.find(f1)->second, name.find(f2)->second);
        }
    }
}

느낀점

  • 해쉬를 오랜만에 사용하다보니 살짝 헷갈리는 부분이 있었다.
  • 계속해서 시간초과가 뜨길래 왜 그런가 하고 봤더니 두 원소가 parent가 같은 원소를 union 시켜버려서 무한루프에 빠져버리는 경우가 발생했다.
  • 다음부터는 union 시킬 때 조심해야겠다!