백준 1992번 : 쿼드트리

  백준 2630번 : 색종이 만들기에 이어서 다음 분할 정복 문제다. 거의 비슷한 문제였기 때문에 2630번의 코드를 그대로 사용했다. (2630번 풀이 : https://stillchobo.tistory.com/72) 2630번과 다른 점은 '0 묶음'과 '1 묶음'의 개수를 세는 것과 다르게 4분할 할 시 괄호를 이용해 구분을 해줘야 한다는 점이다. 그래서 4분할 재귀를 하기 전에 괄호를 열고 닫음으로서 그 부분을 해결했다.

 

  의외로 애 먹었던 지점은 input을 읽는 과정이였는데 처음에는 int로 한 줄을 읽고 10씩 나누면서 배열에 할당했다. 그런데 그렇게 하니까 예제는 잘 되는데 틀렸다고 하길래 '도대체 왜?!'라고 10분 동안 짜증내다가 생각해보니까 64자리 숫자는 int는 커녕 long long으로도 못 읽는다! 엌...... 머쓱타드.... 그래서 결국 string으로 읽고 ASCII 코드 개념을 이용해 '0'을 빼주는 방식으로 읽었다.

 

#include <iostream>
#include <stdio.h>

using namespace std;

int n;
int arr[64][64];

void check(int size, int startX, int startY)
{
    int target = arr[startX][startY];
    
    for(int x = startX; x < startX + size; x++)
    {
        for(int y = startY; y < startY + size; y++)
        {
            if(arr[x][y] != target)
            {
                cout << "(";
                check(size/2, startX, startY);
                check(size/2, startX + size/2, startY);
                check(size/2, startX, startY + size/2);
                check(size/2, startX + size/2, startY + size/2);
                cout << ")";
                
                return;
            }
        }
    }
    
    if(target == 0) cout << "0";
    else cout << "1";
}

int main()
{
    cin >> n;
    
    for(int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        
        for(int j = 0; j < n ; j++)
        {
            arr[j][i] = s[j] - '0';
        }
    }
    
    check(n, 0, 0);
}