인프런 커뮤니티 질문&답변

안녕하세요 큰돌님.

2-E 쿼드 트리 문제 반례를 도저히 못찾겠습니다.

97% 쯤인가 여기서 자꾸 실패가 떠요.백준 질문 게시판에 올라가있는 테스트 케이스를 넣어도 다 통과는 하는데 무슨 반례에 걸리는지 도무지 감이 안잡힙니다.

한번 봐주실 수 있나요?

#include <bits/stdc++.h>

using namespace std;

int N, adj[70][70];
string input;

string go(int sy, int sx, int size)
{
    int ey = sy + (size - 1);
    int ex = sx + (size - 1);
    // cout << sy << " " << sx << " " << ey << " " << ex << '\n';

    if (size == 2)
    {
        if (adj[sy][sx] == adj[sy][ex] && adj[sy][ex] == adj[ey][sx] && adj[ey][sx] == adj[ey][ex] && N > 2)
            return to_string(adj[sy][sx]);
        string subret = "(";
        subret += to_string(adj[sy][sx]);
        subret += to_string(adj[sy][ex]);
        subret += to_string(adj[ey][sx]);
        subret += to_string(adj[ey][ex]);
        subret += ")";
        return subret;
    }

    string lt = go(sy, sx, size / 2);
    string rt = go(sy, sx + size / 2, size / 2);
    string lb = go(sy + size / 2, sx, size / 2);
    string rb = go(sy + size / 2, sx + size / 2, size / 2);

    // cout << "lt: " << lt << " rt: " << rt << " lb: " << lb << " rb: " << rb << '\n';

    if (lt.size() == 1 && lt == rt && rt == lb && lb == rb && N > 2)
        return lt;
    string ret = "(";
    ret += lt;
    ret += rt;
    ret += lb;
    ret += rb;
    ret += ")";
    return ret;
}

int main()
{
    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        cin >> input;
        for (int j = 0; j < N; ++j)
        {
            adj[i][j] = input[j] - '0';
        }
    }
    string ret = "";
    if (N == 1)
        ret = "1";
    else
    {
        ret = go(0, 0, N);
    }
    cout << ret << '\n';

    return 0;
}