[백준] 4195번 친구 네트워크

[적용한 알고리즘]

해싱, 유니온 파인드

 

[아이디어]

[생각의 흐름 / 절차] 

해싱한 뒤에 유니온 파인드를 해주면 된다.

다만 같은 집합이냐만 검사하는 것이 아니라 집합의 크기를 리턴해줘야하므로

그걸 처리해주는 과정이 필요하다. 

 

애초에 parent 배열을 -1로 초기화 해줬고, 

parent 가 root 노드라는 뜻은 parent가 음수라는 뜻이다.

이때 어차피 음수를 사용할 것이니 각 그룹의 root 노드에는 집합의 크기를 저장하도록 하면,

merge 함수에서 parent[x] 에 갱신될 값은

parent[x] (=x가 root 노드인 집합의 크기) + parent[y](=y가 root 노드인 집합의 크기) 가 되겠다.

그럼 집합의 크기를 리턴해줄 때는 루트 노드에 -를 붙인 값을 리턴해주면 된다.

 

[교훈]

이름들을 구분 짓는데 어려움이 있었는데 map 이라는 STL 자료구조가 있어 요긴하게 썼다.

유니온 파인드는 find와 union 에서 문제에서 원하는 값을 담을 수 있게끔 짜는 것이 핵심인 것 같다.

 

<코드>

#include <cstdio>
#include <string>
#include <algorithm>
#include <map>
#define max 200001
using namespace std;

int parent[max];

int find(int x){
    if (parent[x] < 0) return x;
    return parent[x] = find(parent[x]);
}

int merge(int x, int y){
    x = find(x);
    y = find(y);

    if (x == y) return parent[x];

    parent[x] = parent[x] + parent[y];
    parent[y] = x;

    return (-parent[x]);
}

int main(){
    int t; scanf("%d", &t);
    while (t--){
        int f;
        scanf("%d", &f);
        fill(parent, parent + max, -1);

        map<string, int> hash;
        int idx = 0;

        for (int i = 0; i < f; i++){
            char name1[21] = { 0 };
            char name2[21] = { 0 };
            scanf("%s %s", name1, name2);

            if (hash.count(name1) == 0){
                hash[name1] = idx++;
            }
            if (hash.count(name2) == 0){
                hash[name2] = idx++;
            }
            int a = hash[name1];
            int b = hash[name2];

            printf("%d\n", merge(a, b));
        }
    }
    return 0;
}