본인 풀이

#include<bits/stdc++.h>
using namespace std;

int n;
int a[10][10];
int visited[10][10];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

int dfs(int y, int x, int check){
    int ret = 1;
    visited[y][x] = 1;

    for (int i = 0; i < 4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];

        if(ny < 0 || nx < 0 || ny >= n || nx >= n){
            continue;
        }

        // b는 0 또는 1, 0에 해당하는 넓이와 1에 해당하는 넓이를 알기 위함
        // 0인곳만 방문
        if(a[ny][nx] == check && !visited[ny][nx]){
            ret += dfs(ny, nx, check);
        }
    }
    return ret;
}

string compress(int sx,int sy, int n){
    string str = "";
    memset(visited, 0, sizeof(visited));
    if (n == 1)
    {
        return to_string(a[sy][sx]);
    }

    for (int i = sy; i < sy + n; i++)
    {
        for (int j = sx; j < sx + n; j++)
        {
            if (visited[i][j])
            {
                continue;
            }
            int area0 = dfs(i, j, 0);
            int area1 = dfs(i, j, 1);
            // DFS 한번으로 전체 넓이가 n*n이 되지 않으면 컴프레싱
            if(area0 != n * n && area1 != 1){
                str += "(";
                string lefttop = compress(sx, sy, n / 2);
                string righttop = compress(sx + n/2, sy, n/2);
                string leftbottom = compress(sx, sy + n/2, n/2);
                string rightbottom = compress(sx + n/2,sy + n/2, n/2);
                if(lefttop == righttop && righttop == leftbottom && leftbottom == rightbottom){
                    str = lefttop;
                    return str;
                } else {
                    str += lefttop;
                    str += righttop;
                    str += leftbottom;
                    str += rightbottom;
                }
                str += ")";
                return str;
            }
            if (area0 == 1){
                return "1";
            }else{
                return "0";
            }
        }
    }

    return str;
}

// 컴프레싱은 잘 됐는데 괄호삽입이 안됨 - 괄호삽입 기준점 찾기
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    for (int i = 0; i < n; i++){
        string s;
        cin >> s;

        for (int j = 0; j < n; j++){
            a[i][j] = s[j] - '0';
        }
    }
        // 1. DFS 각 area값이 2의 제곱수 -> 컴프레스
        // 2. DFS 각 area값이 2의 제곱이 아님 -> 2로 나누기
    string ret;
    ret = compress(0, 0, n);
    cout << ret << "\n";

    return 0;
}

1. 풀다가 너무 지저분해져서 포기
2. 반례 짜맞추기식으로 풀이하게되었음 (괄호삽입 실패 및 1001 입력 반례 실패)
3. 시작점과 사이즈가 달라지도록 분할정복 재귀는 구현했음

모범 답안

#include<bits/stdc++.h>
using namespace std;

int n;
string s;
char a[101][101];

string quad(int y, int x, int size){
    if(size == 1){
        return string(1, a[y][x]);
    }
    char b = a[y][x];
    string ret = "";

    for (int i = y; i < y + size; i++){
        for (int j = x; j < x + size; j++){
            // 문자 하나만 달라도 오염된 사각형이다
            if(b!=a[i][j]){
                ret += "(";
                ret += quad(y, x, size / 2);
                ret += quad(y, x + size / 2 , size / 2);
                ret += quad(y + size / 2, x, size / 2);
                ret += quad(y + size / 2, x + size / 2, size / 2);
                ret += ")";
                return ret;
            }
        }
    }
    return string(1, a[y][x]);
}

// 컴프레싱은 잘 됐는데 괄호삽입이 안됨 - 괄호삽입 기준점 찾기
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    for (int i = 0; i < n; i++){
        cin >> s;
        for (int j = 0; j < n; j++){
            a[i][j] = s[j];
        }
    }
    cout << quad(0, 0, n) << "\n";

    return 0;
}

복습(7/17)

실패

#include<bits/stdc++.h>
using namespace std;
int n;
int quad[64][64];

string solution(int y, int x, int len){
    string ret = "(";
    if (len == 1){
        return to_string(quad[y][x]);
    }

    bool flag = 0;
    int prev = quad[y][x];
    for (int i = y; i < y + len / 2; i++){
        for (int j = x; j < x + len / 2; j++){
            if(quad[i][j] != prev){
                flag = 1;
                break;
            }
        }
        if(flag){
            break;
        }
    }

    if(flag){
        ret += solution(y, x, len / 2);
    }else{
        ret += to_string(prev);
    }

    flag = 0;
    prev = quad[y][x + len / 2];
    for (int i = y; i < y + len / 2; i++){
        for (int j = x + len / 2; j < x + len; j++){
            if(quad[i][j] != prev){
                flag = 1;
                break;
            }
        }
        if(flag){
            break;
        }
    }

    if(flag){
        ret += solution(y, x + len / 2, len / 2);
    }else{
        ret += to_string(prev);
    }

    flag = 0;
    prev = quad[y + len / 2][x];
    for (int i = y + len / 2; i < y + len ; i++){
        for (int j = x; j < x + len / 2; j++){
            if(quad[i][j] != prev){
                flag = 1;
                break;
            }
        }
        if(flag){
            break;
        }
    }

    if(flag){
        ret += solution(y + len / 2, x, len / 2);
    }else{
        ret += to_string(prev);
    }

    flag = 0;
    prev = quad[y + len / 2][x + len / 2];
    for (int i = y + len / 2; i < y + len ; i++){
        for (int j = x + len / 2; j < x + len; j++){
            if(quad[i][j] != prev){
                flag = 1;
                break;
            }
        }
        if(flag){
            break;
        }
    }

    if(flag){
        ret += solution(y + len / 2, x + len / 2, len / 2);
    }else{
        ret += to_string(prev);
    }

    ret += ")";
    // 최종압축 이후 다시 압축진행
    char prevC = ret[1];
    flag = 0;
    for (char ch : ret){
        if(ch == '(' || ch == ')'){
            continue;
        }
        if(prevC != ch){
            flag = 1;
            break;
        }
    }

    if(!flag){
        ret = "(";
        ret += prevC;
        ret += ")";
        return ret;
    }

    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    string bufferflush;
    getline(cin, bufferflush);

    for (int i = 0; i < n; i++){
        string temp;
        getline(cin, temp);

        for (int j = 0; j < n; j++){
            quad[i][j] = temp[j] - '0';
        }
    }

    cout << solution(0, 0, n) << "\n";

    return 0;
}

1. 1~4사분면 각각 쪼개어 재귀호출했는데, 56%에서 에러 걸렸음.
2. (1111)과 같은 부분에 대해 에러처리를 진행해도 통과하지 못함. 놓친 로직이 있고 코드도 더럽다

#include<bits/stdc++.h>
using namespace std;
int n;
int quad[64][64];
string compress(int y, int x, int len)
{
    string ret;
    bool flag = 0;
    int prev = quad[y][x];

    if(len == 1){
        return to_string(quad[y][x]);
    }

    for (int i = y; i < y + len; i++){
        for (int j = x; j < x + len; j++){
            if(prev != quad[i][j]){
                flag = 1;
                break;
            }
        }
        if(flag){
            break;
        }
    }

    if(flag){
        ret += "(";
        ret += compress(y, x, len / 2);
        ret += compress(y, x + len / 2, len / 2);
        ret += compress(y + len / 2, x, len / 2);
        ret += compress(y + len / 2, x + len / 2, len / 2);
        ret += ")";
    }else{
        ret += to_string(prev);
    }

    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    string bufferflush;
    getline(cin, bufferflush);

    for (int i = 0; i < n; i++){
        string temp;
        getline(cin, temp);

        for (int j = 0; j < n; j++){
            quad[i][j] = temp[j] - '0';
        }
    }

    cout << compress(0, 0, n) << "\n";

    return 0;
}

1. length가 1보다 크면서 모든 요소가 같으면 괄호를 붙이지 않는다.
2. 순회 중인 쿼드트리 요소가 하나라도 오염됨을 파악하는 순간 플래그를 붙이고 순회를 중단한다.
3. 플래그를 가지고 분기처리를 진행한다. 오염된 경우 괄호와 함께 각 사분면에 따라 압축을 진행하고, 아닌 경우 하나로 압축하여 리턴한다.