BOJ 1998번 이미지 압축

이 문제는 흔히 가로외 세로의 길이가 같은 격자판에서 각 칸이

검은색 또는 흰색으로 이루어져 있을때 자식이 4개이거나 0개인

트리로 격자를 표현하는 '쿼드 트리' 라는 개념의 변형 문제이다.

격자가 주어졌을때 이 격자를 가장작은 정사각형모양으로 키우고

새로생긴 격자를 흰색으로 채운 뒤

쿼드트리의 노드의 개수를 구하는 것이 첫번째 요구되어지는 것이고

그다음엔 압축된 쿼드트리의 노드 수를 구해야 하는데

압축을 하는 방법은 공통된 서브 트리들을 딱 하나만남겨서 공유하는 것이다.

이렇게 할때 최소한의 노드 수를 사용하도록 압축했을 때의

노드의 수를 구하는 것이 두번째 요구되어지는 답이다.

우선 복잡도 계산을 위해 총 노드 수의 상한을 계산해보자.

격자의 가로 세로 길이는 128이 최대이기 때문에 쿼드트리의 높이는

최대 7일 것이다. 그러므로 꽉찬 트리일때 1+4^1+4^2+...+4^7 개의 노드이므로

(4^8-1)/3 개, 즉 21845개가 최대이다.

우선 쿼드 트리로 나타내는 것은 쉽다.

현재 보고있는 정사각형의 왼쪽 위의 좌표와 한 변의 길이를 인자로

재귀호출을 하면 보고있는 정사각형의 모든 칸이 같은 색이라면

리프노드이기때문에 반환, 다 같지않다면 네 개의 정사각형에 대해

서브호출을 하면 끝이다. 적절히 리턴값을 주거나 배열의 값에 기록을 하여

일반 쿼드트리로 나타낼때의 총 노드 수를 구하는 것은 어렵지않다.

그렇다면 압축된 쿼드트리의 노드수는 어떻게구할수가 있을까?

dfs 를 돌리며 현재 보고있는 노드를 루트로 갖는 서브 트리가

이전에 나왔는지를 체크해서 나왔으면 0을 반환, 안나왔으면

현재 서브트리가 나왔다는 것을 기록하고

1에 네개의 쪼개진 정사각형에 대해 서브호출한값들을 누적하여

반환하면 될 것이다. 그런데 이미 나왔다는 것을

어떻게 기록을 하며, 기록되어진 것들 중에서 같은 트리가 있는지

어떻게 비교를 할까? 가장 naive 한 방법은

우선 각각의 노드를 루트로 갖는 서브트리의 총 노드수와 높이를 구해놓고

최대 약 21000개의 서브트리가 있을 텐데  앞에서 탐색한 모든 노드들에 대해

총 노드수와 높이가 같은 모든 서브 트리들에 대해

dfs를 돌리며 나와 같은지 비교를 할 수가 있다.

구현을 쉽게하기 위해서 쓸수있는 한가지 방법이

쿼드트리는 전위 순회 순서대로 1자로 펼쳐서 문자열 형태로 만들 수가

있다는 것이다. 우선 각 노드의 값은 세개 중에 하나이기 때문에

숫자와 알파벳만해도 62개인 문자로 충분히 표현이 가능하다.

그럼 앞에 나온 서브트리들에 대해

모두 dfs를 돌리는 대신 단순히 노드별로 펼친 문자열을

미리 구해놓고(dfs(재귀함수)를 미리한번돌려놓음)

문자열 비교를 하면 된다.

그런데 문자열끼리 비교하는 데에는 선형시간이 들기 때문에

시간 안에 돌아갈 지는 미지수..(사실 안해봤다)

그니까 해싱을 쓰자! 트리 전체를 해싱하여 unordered_map 을 이용하여

이전에 나왔던 트리인지 상수시간에 체크가 가능하다

트리 전체를 해싱하는 방법은 여러가지가 있겠지만

쿼드트리에서 뿐만 아니라 일반 트리에서까지 확장하자면

하나의 트리를 펼쳐 문자열로 생각하여 모든 자식들에 대해 이어 붙이는 것인데

노드의 값이 아스키코드의 종류 수를 넘는 경우도 있을 수 있는데

base^k 에 대해 모듈러값을 미리 다 구해놓고

지금 보는 서브트리의 노드수 승 만큼

현재 누적값 해쉬값을 올려주고 현재 보는 서브트리의 해쉬값을 더해주는식으로

반복해 주면 되지만, 한가지 처리를 해줘야 한다.

쿼드트리일땐 자식의 순서가 중요하므로 그냥하면 되지만

일반 트리에서는 자식의 순서가 바뀌어도 결국 같은 트리이기 때문에

자식을 보는 순서를 강제해줄 필요가 있는데 단순하다, 그냥 해쉬값으로

정렬하여 순서대로 붙여주면 된다.

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define inp5(a,b,c,d,e) scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;    
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
typedef vector<piii> viii;
const double EPSILON = 1e-9;
const double PI = acos(-1);
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;
const int ADD = 32741;
 
ll h[129][129][129];
string qStr[129][129][129];
int isLeaf[129][129][129];
int pane[129][129];
int N, M;
int dy[] = {0, 0, 1, 1};
int dx[] = {0, 1, 0, 1};
map<ll, int> mp;
ll hashFunc(string str){
    ll ret = 0;
    for(int i = 0; i < str.size(); i++){
        ret = (ret * ADD + str[i]) % MOD;
    }    
    return ret;
}
int go(int posI, int posJ, int size){
    int start = pane[posI][posJ];
    bool allSame = true;
    for(int i = posI; i < posI + size; i++){
        for(int j = posJ; j < posJ + size; j++){
            if(start != pane[i][j]) allSame = false;
        }
    }
    string& here = qStr[posI][posJ][size];
    if(allSame){
        isLeaf[posI][posJ][size] = 1;
        here = (pane[posI][posJ] == 0 ? "W" : "B");
        return 1;
    }
 
    here = "X";
    int ret = 1;
    FOR(k,4){
        int s = size/2;
        string& next = qStr[posI + dy[k]*s][posJ + dx[k]*s][s];
        ret += go(posI + dy[k]*s, posJ + dx[k]*s, s);
        here += next;
    }
    return ret;
}
 
int dfs(int posI, int posJ, int size){
    if(isLeaf[posI][posJ][size]) return 1;
    if(mp[hashFunc(qStr[posI][posJ][size])]) return 0;
    mp[hashFunc(qStr[posI][posJ][size])] = 1;
 
    int ret = 1;
    FOR(k,4){
        int s = size/2;
        ret += dfs(posI + dy[k]*s, posJ + dx[k]*s, s);
    }
    return ret;
}
int main() {
    memset(pane,-1,sizeof(pane));
    memset(isLeaf,0,sizeof(isLeaf));
    inp2(N,M);
    FOR(i,N){
        FOR(j,M){
            scanf("%1d",&pane[i][j]);
        }
    }
 
    M = (1<<(int)(ceil(log2(M))));
    N = (1<<(int)(ceil(log2(N))));
 
    M = N = max(N,M);
 
    FOR(i,N){
        FOR(j,M){
            if(pane[i][j] == -1) pane[i][j] = 0;
        }
    }
 
    int ans1 = go(0,0,N);
    int ans2 = dfs(0,0,N);
    printf("%d %d\n",ans1,ans2);
 
    return 0;
}