1992 쿼드트리

www.acmicpc.net/problem/1992

1992번: 쿼드트리

<아이디어>

알고리즘 문제해결전략 책에 소개된 알고스팟 문제와 유사한 문제이다.

damper.tistory.com/4

[ALGOSPOT] QUADTREE

전형적인 분할정복 문제.

문제를 4부분으로 쪼갠 후 (좌상 우상 좌하 우하), 각 부분을 모두 0이거나 1일때까지 계속해서 4부분으로 쪼갠다.

모두 0이거나 1인 부분이 나오면 (또는 나눈 부분의 크기가 1인 부분) 그대로 해당 문자를 return 한다.

return을 받았다면 4부분을 합쳐서 다시 return 한다.

 

최종적으로 return 한 문자열을 출력하면 끝.

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
string div_s(vector<string>& v, int size, int y, int x)
{
    bool flag = true;
    for(int i=y;i<y+size;i++)
        for(int j=x;j<x+size;j++)
            if(v[i][j]!=v[y][x]) flag = false;
    if(flag) return string(1, v[y][x]);
    size /= 2;
    return "("+div_s(v, size, y, x)+div_s(v, size, y, x+size)+
    div_s(v, size, y+size, x)+div_s(v, size, y+size, x+size)+")";
 
}
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n;
    cin>>n;
    vector<string> v(n, "");
    for(int i=0;i<n;i++)
        cin>>v[i];
    cout<<div_s(v, n, 0, 0);
    
    return 0;
}