[매일1문제] BOJ 4195 - 친구네트워크

매일 1문제라는 프로젝트명이 무색하게 근 2주일만에 문제를 풀었다.
그 이유는 막학기지만 대학생의 바쁨을 너무 얕봤기 때문,,,,
그리고 청천벽력같은 소식이라면, 이제 이 프로젝트를 할 때 반드시.. STL을 쓰지 않아야 한다는 조건이 생겼다.. ㅎ…

문제

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

아이디어

문제 자체는 단순한 유니온-파인드 문제다.
다만 같은 트리에 속하는 노드의 개수를 어떻게 세느냐가 문제였는데, 각 노드에 해당 노드가 루트였을 때 원소 개수를 저장하고 합칠 때 가장 최상위 노드끼리 연산하는 방식으로 해결했다.
무조건 그 트리의 원소 수는 해당 트리의 루트에서만 구할 수 있도록 하여, 루트가 아니게 된 이후는 더이상 그 노드에 적혀있는 원소 개수가 의미를 갖지 않는다.

구현

이 문제를 푸는 목적은 해시테이블의 구현에 대해 익숙해지는 것이었기 때문에, 우선 STL을 이용해 구현한 이후 해시테이블을 접목해 변형하는 방법을 선택했다.
우선 해시테이블을 처음부터 혼자 구현한다는 것은 나에게는 불가능한 일이었다.
다행스럽게도 시험을 볼 때 레퍼런스 코드가 주어진다고 하였고, 정확히 어떤건지는 모르기 때문에 일단 홈페이지의 레퍼런스 코드란에 있는 코드는 무조건 이용하기로 했다.(절대 공부를 더 하기 싫어서가 아니다)
가장 처음에는 기본적으로 주어진 해시테이블 구조를 사용해 풀어보았는데, 아니나 다를까 시간초과!(예정된 수순이었다.)
사실 레퍼런스 코드가 있다는 것을 알기 전에 직접 구현해보려고 찾아놓았던 블로그가 있는데, 이 곳의 설명을 참고하여 체이닝 기법을 사용했다.
구현하면서 정말 많은 문제가 있었는데.. 그중 가장 큰 문제는 동적할당을 이용하면서 일어나는 문제였다.
생성자를 만들어두긴 했지만, new를 사용하지 않고 malloc만 이용할 경우 생성자가 할당되지 않는다는 엄청난 문제가 발생한다.
그래서 일단 new를 이용해 죄다 객체선언을 하긴 했는데.. 실제 시험 환경에서도 new가 사용이 가능한지 모르겠다..!
만일 전역변수가 사용 가능하다면 문제가 없지만, 이번 문제처럼 여러 개의 테스트케이스가 주어져 초기화가 필수적일 경우 각 노드를 전부다 돌면서 일일이 초기화를 해줘야 할 것 같다.
malloc-free나 new-delete의 경우 모두 그동안 잘 사용하지 않아 어색한 문법이므로(새삼 쉬운 알고리즘만 푼 코딩 초짜라는 사실이 느껴진다..) 앞으로 연습하면서 좀 더 익숙해져야 할 것 같다!!

결과

STL 사용 시

메모리 : 23940KB
시간 : 520ms

직접 구현했을 때

메모리 : 17448KB
시간 : 108ms

다음 문제를 곧바로 풀지 않고, 여기서 더 최적화할 수 있는 방법을 더 고민해보는 편이 좋을 것 같다.

소스코드(STL 사용)

#include <iostream>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<string, int> P;

map<string, P> par;

P find(string x) {
    if (par.find(x) == par.end()) {
        return par[x] = { x, 1 };
    }
    else if (par[x].first == x) {
        return par[x];
    }
    return par[x] = find(par[x].first);
}

void merge(string x, string y) {
    P xp = find(x), yp = find(y);
    par[yp.first].second += xp.second;
    yp.second += xp.second;
    par[xp.first] = yp;
}

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        par.clear();
        int f;
        cin >> f;
        for (int i = 0; i < f; i++) {
            string s1, s2;
            cin >> s1 >> s2;
            if (find(s1).first != find(s2).first) {
                merge(s1, s2);
            }
            cout << find(s1).second << "\n";
        }

    }
    return 0;
}

소스코드(해시테이블 구현)

#include <iostream>
#include <stdlib.h>
#define MAX_KEY 20
#define MAX_TABLE 200005

typedef struct Hash
{
    char key[MAX_KEY + 1];
    Hash* next, * parent;
    int cnt;
    Hash() {
        next = nullptr;
        parent = nullptr;
        key[0] = NULL;
        cnt = 1;
    }
}Hash;

Hash* tb;
int par[MAX_TABLE][2]; // [0]:par [1]:cnt

unsigned long hash(const char* str)
{
    unsigned long hash = 401;
    int c;

    while (*str != '\0') {
		hash = ((hash << 4) + (int)(*str)) % MAX_TABLE;
		str++;
	}

    return hash % MAX_TABLE;
}

bool stringCompare(const char* x, const char* y) {
    bool rtn = true; // 같을 경우
    int i = 0;
    for (i = 0; x[i] && y[i]; i++) {
        if (x[i] != y[i]) {
            rtn = false;
            return rtn;
        }
    }
    if (x[i] != y[i]) {
        rtn = false;
    }
    return rtn;
}

void stringCopy(char* dist, const char* value) {
    int i = 0;
    for (i = 0; value[i]; i++) {
        dist[i] = value[i];
    }
    dist[i] = NULL;
}

Hash* findNode(const char* key)
{
    unsigned long h = hash(key);
    Hash* it = &tb[h];
    while (it->key[0] != 0)
    {
        if (stringCompare(it->key, key)) {
            return it;
        }
        if (it->next == nullptr) {
            return nullptr;
        }
        it = it->next;
    }
}

Hash* add(const char* key)
{
    unsigned long h = hash(key);
    Hash* rtn;

    if (stringCompare(tb[h].key, key)) {
        return nullptr;
    }

    if (tb[h].key[0] != 0) {
        Hash* it = &tb[h];
        while (it->next) {
            it = it->next;
        }
        Hash* node = new Hash;
        stringCopy(node->key, key);
        it->next = node;
        rtn = node;
    }

    else {
        stringCopy(tb[h].key, key);
        rtn = &tb[h];
    }
    rtn->parent = rtn;
    return rtn;
}

Hash* find(const char* x) {
    Hash* it = findNode(x);
    if (it == nullptr) {
        it = add(x);
        return it;
    }
    else if (it->parent == it) {
        return it;
    }
    Hash* rtn = find(it->parent->key);
    it->parent = rtn;
    return rtn;
}

void merge(const char* x, const char* y) {
    Hash* xp = find(x), * yp = find(y);
    yp->cnt += xp->cnt;
    xp->parent = yp->parent;
    xp->cnt = yp->cnt;
}

int main(void) {
    int T;
    scanf("%d", &T);
    while (T--) {
        tb = new Hash[MAX_TABLE];
        //tb = (Hash*)malloc(sizeof(Hash) * MAX_TABLE);
        int f;
        scanf("%d", &f);
        for (int i = 0; i < f; i++) {
            char s1[25] = { NULL, }, s2[25] = { NULL, };
            scanf("%s %s", s1, s2);
            if (find(s1)->key != find(s2)->key) {
                merge(s1, s2);
            }
            printf("%d\n", find(s1)->cnt);
        }
        //free(tb);
        delete[] tb;
    }
    return 0;
}

[참고]
레퍼런스코드
해시테이블
C/C++에서 해시 테이블 구현하기