[BOJ] 친구 네트워크

친구 네트워크

문제 링크 

어떻게 풀까?

이 문제는 disjoint set과 해쉬를 이용해서 문제를 풀면 됩니다!

위 두개의 방법에 대해서는 나중에 또 올리도록 하겠습니다!

문제를 푸는 방법을 알려드리겠습니다!

disjoint set과 해쉬의 자세한 설명은 생략하겠습니다!

분명! 언젠가 이 방법들에 대해 자세히 설명하는 날이 올 것입니다.. 흑!

링크 꼭 달아드릴게요

우선, disjoint set을 하기 위해서 각각의 아이디를 해쉬를 통해서 인덱스에 저장해 놓는 것이 중요합니다!

그리고, disjoint set을 이용해서 입력받은 두 아이디를 집합으로 만들고, 만들어진 집합의 크기를 출력하시면 문제가 풀리게 됩니다!

예제를 통해서 설명해 드리겠습니다!

처음에 해쉬는 모두 empty 상태이고, 집합은 -1로 초기화 합니다!

집합이 -1이라는 것은, 집합의 크기가 1이라는 것입니다.

그리고 집합의 크기가 0 이상인 경우에는, 해당 값이 바로 부모의 인덱스라는 뜻입니다!

이렇게 설정해 놓으면 집합의 크기도 구하기 쉽습니다!

처음에 Fred와 Barney라는 아이디를 입력받습니다.

두 아이디는 해쉬에 존재하지 않으므로, 해쉬에 두 아이디에 대한 인덱스의 정보를 넣습니다!

이제 Fred는 0번 아이디이고, Barney는 1번 아이디 입니다!

다음은 0번과 1번의 집합을 합칩니다!

0번 아이디와 2번 아이디는 크기가 2인 집합이 되고, 해당 집합의 대표를 0번으로 합니다!

Barney와 Betty를 입력받습니다!

Barney는 이미 해쉬에 1번 아이디라는 정보가 저장되어있습니다.

그리고, Betty는 해쉬에서 찾을 수 없기 때문에 2번 아이디로 설정합니다.

그리고, 둘을 하나의 집합으로 합칩니다!

이 떄, 1번 아이디는 0번 아이디와 이미 집합이었기 때문에 사이즈는 3이 되고, 2번 아이디의 부모를 0번 아이디로 설정합니다.

위와 같은 과정을 반복하면 4개의 친구가 모두 같은 네트워크로 묶이게 되고, 해당 크기는 4가 됩니다!!

코드

//https://www.acmicpc.net/problem/4195
#pragma once
#pragma once
#include<cstdio>
 
const int MAX = 400000;
typedef struct R {
    char *key;
    int value;
};
 
struct NODE {
    char key[21];
    int value;
    NODE* next;
    NODE* prev;
    NODE() {
        value = 0;
        prev = next = 0;
    }
} nodes[MAX];
 
struct MYAL {
    int size;
    void clear() {
        size = 0;
    }
 
    NODE* alloc() {
        return &nodes[size++];
    }
}al;
 
 
int strcmp(const char* c1, const char* c2) {
    int i = 0;
    while (c1[i] && c2[i] && (c1[i] == c2[i])) {
        i++;
    }
 
    return c1[i] - c2[i];
}
 
struct List {
    NODE *head, *tail, *cursor;
    List() {
        head = al.alloc();
        tail = al.alloc();
        head->next = tail;
        tail->prev = head;
    }
 
    void clear() {
        head = al.alloc();
        tail = al.alloc();
        head->next = tail;
        tail->prev = head;
    }
 
    void insert(const char* key, const int value) {
        NODE* nn = al.alloc();
        int i = 0;
        while (key[i]) {
            nn->key[i] = key[i];
            i++;
        }
        nn->key[i] = 0;
        nn->value = value;
 
        nn->next = tail;
        nn->prev = tail->prev;
 
        tail->prev->next = nn;
        tail->prev = nn;
    }
 
    void del() {
        if (cursor == head) return;
 
        cursor->prev->next = cursor->next;
        cursor->next->prev = cursor->prev;
        cursor = cursor->prev;
 
    }
 
    void init() {
        cursor = head;
    }
 
    R next() {
        if (cursor->next == tail) {
            return { 0,-1 };
        }
 
        cursor = cursor->next;
        return { cursor->key, cursor->value };
    }
};
 
int len;
int p[200000]; // -는 사이즈의 크기! +는 부모!
int conv[256] = { 0 }; 
 
struct Hash {
    const int size = 100000;
    List li[100000];
 
    int hash(const char *key) {
        int k = 0;
        while (*key) {
            k *= 52;
            k += conv[*key];
            k %= size;
            key++;
        }
        return k;
    }
 
    int find(const char * key) {
        R a;
        int k = hash(key);
        li[k].init();
 
        while ((a = li[k].next()).key) {
            if (strcmp(key, a.key) == 0) {
                return a.value;
            }
        };
 
        insert(key, len);
        int res = len++;
 
        return res;
    }
 
    void insert(const char* key, const int value) {
        int k = hash(key);
        li[k].insert(key, value);
    }
 
    void clear() {
        al.clear();
 
        for (int i = 0; i < size; i++) {
            li[i].clear();
        }
    }
}hash;
 
void swap(int& i1, int &i2) {
    int temp = i1;
    i1 = i2;
    i2 = temp;
}
 
int getParent(int i) {
    if (p[i] < 0) return i;
 
    return p[i] = getParent(p[i]);
}
 
int join(int i1, int i2) {
    int p1 = getParent(i1);
    int p2 = getParent(i2);
 
    if (p1 == p2) return -p[p1];
    else {
        if (p[p1] > p[p2]) {
            swap(p1, p2);
        }
 
        p[p1] += p[p2];
        p[p2] = p1;
        return -p[p1];
    }
}
 
int main() {
    char in[2][21];
    int t, m;
    int l = 0;
    for (int i = 'a'; i <= 'z'; i++) {
        conv[i] = l++;
    }
 
    for (int i = 'A'; i <= 'Z'; i++) {
        conv[i] = l++;
    }
 
    scanf("%d\n", &t);
    while (t--) {
        scanf("%d\n", &m);
        hash.clear();
        for (int i = 0; i < 2*m; i++) p[i] = -1; // 초기화
        len = 0;
 
        while (m--) {
            scanf("%s %s\n", in[0], in[1]);
            //해쉬를 통해 인덱스를 받는다.
            int i1 = hash.find(in[0]);
            int i2 = hash.find(in[1]);
 
            //disjoint 한다! 그리고 해당 크기를 반환받는다.
            int res = join(i1, i2);
            printf("%d\n", res);
        }
    }
 
    return 0;
}

여담

시간 복잡도는 해쉬를 통해 인덱스를 만드는데 O(1)의 시간이 걸리고,

disjoint 하는 데에 log n 의 시간이 걸리기 때문에 O(log n) 입니다!