백준 1992 (쿼드 트리) c++

문제

1992번: 쿼드트리

분할정복 문제입니다.

n * n (n은 2의 거듭제곱수) 주어지면 전체가 0일 경우 0을 출력하고 1이면 1을 출력합니다.

1과 0이 섞여 있으면 n * n 크기를 4등분 해주어 다시 탐색합니다.

위의 배열은 0과 1이 섞여 있으므로 4등분 해줍니다.

이를 계속 해서 반복하면

다음과 같이 나뉘어 지고

(0(0011)(0(0111)01)1) 가 답이 됩니다.

void divide(int left, int right, int up, int down) {
    ans = arr[up][left];
    flag = true;
    for (int i = up; i < down; i++) {
        for (int j = left; j < right; j++) {
            if (arr[i][j] != ans) {
                flag = false;
                break;
            }
        }
        if (flag == false)
            break;
    }
    if (flag == true) {
        cout << ans;
        return;
    }
    else {
        cout << '(';
        divide(left, (left+right)/2, up, (up+down)/2);
        divide((left+right)/2, right, up, (up+down)/2);
        divide(left, (left+right)/2, (up+down)/2, down);
        divide((left+right)/2, right, (up+down)/2, down);
    }
    cout << ')';
}
 

분할정복하는 함수입니다.

함수의 인자 left, right, up, down은 사각형의 크기를 나타내어 줍니다.

2번째 줄을 보면 ans는 사각형의 가장 왼쪽 위의 수를 의미합니다. 

따라서 ans와 다른 수들이 나오면 0과 1이 섞여 있다는 의미이므로 다시 사각형을 분할하여 줍니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
#define inf INT_MAX
using namespace std;
using ll = long long;
using ull = unsigned long long;
int n;
string str[65];
int arr[65][65];
int ans;
bool flag = false;
void divide(int left, int right, int up, int down);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> str[i];
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            arr[i][j] = str[i][j] - '0';
        }
    }
 
    divide(0, n,0, n );
 
 
    return 0;
}
void divide(int left, int right, int up, int down) {
    ans = arr[up][left];
    flag = true;
    for (int i = up; i < down; i++) {
        for (int j = left; j < right; j++) {
            if (arr[i][j] != ans) {
                flag = false;
                break;
            }
        }
        if (flag == false)
            break;
    }
    if (flag == true) {
        cout << ans;
        return;
    }
    else {
        cout << '(';
        divide(left, (left+right)/2, up, (up+down)/2);
        divide((left+right)/2, right, up, (up+down)/2);
        divide(left, (left+right)/2, (up+down)/2, down);
        divide((left+right)/2, right, (up+down)/2, down);
    }
    cout << ')';
}