쿼드트리

• 깨달음
  char[][] 배열로 문자열을 입력받을 때에는
  반드시 +1만큼 더 크게 해야한다
  --> 마지막에 null문자가 삽입되기 때문에!!!
  안그러면 참조가 벗어나서 BOJ에서 메모리 초과라고 뜬다!

코드

[ int 배열로 받을 때 ]

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// 1:46 ~
string ans="";
int board[64][64];
bool check(int y, int x, int size){
    int fix = board[y][x];
    for(int i=y;i<y+size;i++)
    {
        for(int j=x;j<x+size;j++)
        {
            if(fix != board[i][j]) return false;
        }
    }
    return true;
}
void zip(int y, int x, int size)
{
    bool result = check(y, x, size);
    if(result)
    {
        if(board[y][x])
            ans += "1";
        else ans += "0";
    }else if(size > 1){
        /* 1사분면 */
        ans += "(";
        zip(y, x, size/2);
        /* 2사분면 */
        zip(y, x+size/2, size/2);
        /* 3사분면 */
        zip(y+size/2, x, size/2);
        /* 4사분면 */
        zip(y+size/2, x+size/2, size/2);
        ans += ")";
    }
    return;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        string S; cin >> S;
        for (int j = 0; j < S.length(); j++)
            board[i][j] = S[j] - '0';
    }
    zip(0, 0, N);
    cout << ans;
    return 0;
}

---

[ char배열로 받을 때 ]

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// 1:46 ~
string ans="";
char board[64][64];
bool check(int y, int x, int size){
    char fix = board[y][x];
    for(int i=y;i<y+size;i++)
    {
        for(int j=x;j<x+size;j++)
        {
            if(fix != board[i][j]) return false;
        }
    }
    return true;
}
void zip(int y, int x, int size)
{
    bool result = check(y, x, size);
    if(result)
    {
        if(board[y][x] == '1')
            ans += "1";
        else ans += "0";
    }else if(size > 1){
        /* 1사분면 */
        ans += "(";
        zip(y, x, size/2);
        /* 2사분면 */
        zip(y, x+size/2, size/2);
        /* 3사분면 */
        zip(y+size/2, x, size/2);
        /* 4사분면 */
        zip(y+size/2, x+size/2, size/2);
        ans += ")";
    }
    return;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            cin >> board[i][j];
    zip(0, 0, N);
    cout << ans;
    return 0;
}

• 주의할 점 !

    for(int i=0;i<N;i++)
            cin >> board[i];

: 기존에 입력을 이렇게 받았더니 에디터에서는 잘돌아가는데,
BOJ 제출시 메모리 초과가 떴다.
-->
이유는??? char[][] 사용시 마지막에 널문자를 고려해야 해서 원하는 크기보다 +1 만큼 더 필요하다!!