1992번

1992번 - 쿼드 트리

분할 정복 문제. 말 그대로 분할해서 문제를 풀고 합친다.

반복 되는 부분을 재귀로 구현했다.

주어진 영상이 하나의 수로만 표현되어 있지 않다면 !perfect 로 4분할을 하게 된다.

하지만 영상이 하나의 수로 perfect 하다면 그 숫자를 출력하면 된다.

string 쓰는 법을 잘 몰라서 그냥 + 로 계속 덧 붙여서 저장하였다.

함수의 인자로는 시작하는 x좌표 sx, 시작하는 y좌표 sy, 맵의 크기 N으로 구성하였다.

재귀는 단순하게 생각하자... 재귀는 단순하게...

<정답 코드>

#include<iostream>
#include<string>

using namespace std;
int N;
int map[65][65];
int dx[4] = { 0,0,1,1 };
int dy[4] = { 0,1,0,1 };

string ans;
void dnc(int sx, int sy, int n)
{
    bool perfect = true;
    for (int i = sx; i < sx + n; i++)
    {
        for (int j = sy; j < sy + n; j++)
        {
            if (map[sx][sy] != map[i][j])
            {
                perfect = false;
            }
        }
    }
    if (!perfect)
    {
        ans += '(';
        for (int d = 0; d < 4; d++)
        {
            int nx = sx + dx[d] * (n / 2);
            int ny = sy + dy[d] * (n / 2);
            dnc(nx, ny, n / 2);
        }
        ans += ')';
        return;
    }
    if (perfect)
    {
        ans += map[sx][sy] + '0';
        return;
    }
}
int main()
{
    //freopen("input.txt", "r", stdin);
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            char tmp;
            cin >> tmp;
            map[i][j] = tmp - '0';
        }
    }
    dnc(0, 0, N);
    cout << ans << endl;
}