[BOJ 2379] 트리 탐색하기

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

2379번: 트리 탐색하기

Tag : hash

 

문제요약

트리가 이진수의 형태로 주어졌을 때 두 트리가 동형인지 판별하라.

 

풀이

서브트리들을 재귀적으로 어떠한 기준에 의해 잘 정렬하면 두 트리가 같은지 판별할 수 있다.

( (XXX) (X) (XXXX) ) 에서 X들을 감싸는 서브트리의 내부가 잘 정렬되어있다고 가정하면

(XXX), (X), (XXXX)를 동일한 기준으로 정렬해서 나온 결과는 한가지 형태의 트리에서 유일할 것이다.

이 기준은 바이트 문자열로 입력이 주어졌기 때문에 이것을 그대로 사용해도 된다. 

 

나는 굳이 이것을 다시 트리로 복원해서 해싱을 새로 했다.... 뇌절....

 

해싱은 라빈카프 하듯이 할 수 있다. (사실 라빈카프 형태도 짜본적 없음...)

hash[x] = 1) 크기가 1인 트리라면 1

                 2) 서브트리들을 hash기준으로 정렬한 상태에서 \(\sum{ hash_i * base^i } mod P\)

나쁜 출제자들이 유명한 소수들에 대해 반례를 넣어놨을 수 있기 때문에 소수 3개에 대해 구했다.

 

한쪽 트리는 루트를 아무거나 잡고  나머지 트리에서는 모든 정점을 루트로 만들어보면서 판단할 수 있다.

-> \(O(N^2logN)\)

 

또는 양쪽 트리의 센트로이드를 구해서 한번씩만 돌릴 수도 있다. 

센트로이드가 2개일 때는 두개 중 min max 중 하나를 비교하거나

센트로이드가 항상 인접하다는 것을 이용해 정점을 두개로 쪼개고 하나의 센트로이드를 새로 만들 수도 있다.

-> \(O(NlogN)\)

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'

using namespace std;
using ll = long long;

struct TREE{
    int n; int root;
    vector<vector<int>> v;
    vector<int> sz, cent;
    TREE(string s) {
        v.resize(3030); sz.resize(3030);
        vector<int> st; n = 1; st.push_back(0); root = 0;
        for(int i=0; i<s.size(); i++) {
            if(s[i] == '0') {
                v[st.back()].push_back(n);
                v[n].push_back(st.back());
                st.push_back(n++);
            } else st.pop_back();
        }
        getCent();
        if(cent.size() == 2) {
            root = n;
            v[cent[0]].push_back(n);
            v[n].push_back(cent[0]);
            v[cent[1]].push_back(n);
            v[n].push_back(cent[1]);
            vector<int> a, b;
            for(auto &i : v[cent[0]]) {
                if(i == cent[1]) continue;
                a.push_back(i);
            }
            for(auto &i : v[cent[1]]) {
                if(i == cent[0]) continue;
                b.push_back(i);
            }
            v[cent[0]].clear();
            for(auto &i : a) v[cent[0]].push_back(i);
            v[cent[1]].clear();
            for(auto &i : b) v[cent[1]].push_back(i);
            n++;
        }
    }
    int getCent(int x = 0, int p = -1) {
        sz[x] = 1;int mx = 0;
        for(auto &i : v[x]) if(i != p) {
            sz[x] += getCent(i, x);
            mx = max(mx, sz[i]);
        }
        if(mx * 2 <= n and 2 * (n - sz[x]) <= n) cent.push_back(x);
        return sz[x];
    }
    int hash(ll MOD, int x = 0, int p = -1) {
        vector<ll> sub;
        for(auto &i : v[x]) if(i != p) {
            sub.push_back(hash(MOD, i, x));
        }
        sort(sub.begin(), sub.end());
        ll ret = 1, base = 1109;
        for(auto &i : sub) {
            ret = (ret * base % MOD + i) % MOD;
        }
        return ret;
    }
};

#include <unistd.h>
#include <sys/stat.h>
#include <sys/mman.h>
char O[2000000],*d=O;
template<class T> inline void p(T x) {
    if(x<0) *d++='-', x=-x;
    char t[16], *q=t;
    do *q++=x%10|48; while(x/=10);
    do *d++=*--q; while(q!=t);
    *d++=10;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    int tc; cin >> tc;
    while(tc--) {
        string a, b; cin >> a >> b;
        shared_ptr<TREE> x = make_shared<TREE>(a);
        shared_ptr<TREE> y = make_shared<TREE>(b);
        if(x->n != y->n) {
            cout << 0 << endl;
            continue;
        }
        ll M1 = 998244353;
        ll M2 = 2483027969;
        ll M3 = 104857601;
        int f = 0;
        ll t1 = x->hash(M1, x->root, -1);
        ll t2 = x->hash(M2, x->root, -1);
        ll t3 = x->hash(M3, x->root, -1);
        ll p1 = y->hash(M1, y->root, -1);
        ll p2 = y->hash(M2, y->root, -1);
        ll p3 = y->hash(M3, y->root, -1);
        if(t1 == p1 and t2 == p2 and t3 == p3) f = 1;
        p(f);
    }
    write(1, O, d - O);
}