[백준 1992번] 쿼드트리

http://www.acmicpc.net/problem/1992

1992번: 쿼드트리

풀이) 

c로 입력받을 때는 1개씩 끊어서 받기위해서 "%1d"을 사용하면 되지만, cpp에선 되지않는다. 이럴 때 char tmp;를 하나 선언해놓고 한개씩 받는 방법도 사용해볼 수 있다. 1780(종이의 개수)와 비슷한 분할정복문제였고, 해당 크기가 같지 않으면 재귀 앞뒤로 (, )출력해주고 4곳 좌표 잡아서 재귀를 돌려주면 된다.

 

#include <iostream>
using namespace std;

int map[65][65];

void recursive(int x, int y, int size)
{
    int temp = map[x][y];
    for (int i = x; i < x + size; i++)
    {
        for (int j = y; j < y + size; j++)
        {
            if (temp != map[i][j])
            {
                cout << "(";
                recursive(x, y, size / 2);
                recursive(x, y + size / 2, size / 2);
                recursive(x + size / 2, y, size / 2);
                recursive(x + size / 2, y + size / 2, size / 2);
                cout << ")";
                return ;
            }
        }
    }
    cout << temp;
}

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

    int N;
    char a;
    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cin >> a;
            map[i][j] = a - '0';
        }
    }
    recursive(1, 1, N);
    return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!