BOJ 1992 쿼드트리

문제 링크 : https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

요약

BOJ 1780 종이의 개수와 매우 유사한 문제

0, 1로 이루어진 N x N의 행렬이 있을 때  전체 영역이 모두 같은 값이라면 한 개로 압축하고,

그게 아니라면 가로 2, 세로 2 영역으로 4등분하여 각 영역이 모두 같은 값으로 이루어질 때까지 나누었을 때  압축한 결과를 괄호에 싸서 출력하는 문제.

풀이

전형적인 분할정복 문제!! 부분 행렬의 전부를 탐색했을 때 모두 같은 값이라면 한 개로 압축하도록 기저를 잡고 그게 아니라면 재귀 함수를 이용해서 4 등분하여 조건에 해당하는지 확인하고 각 영역의 답을 모두 합병해준다. 재귀 함수를 돌리기 전에 괄호를 넣어주고 재귀가 끝날 때 괄호를 닫아준다.

 

코드

#include<iostream>
using namespace std;
int n, arr[65][65];
int ans[3];
void sol(int d, int r, int cnt) {
    int num = arr[d][r];
    int chk = -1;
    for (int i = d; i < d + cnt; i++) {
        for (int j = r; j < r + cnt; j++) {
            if (num != arr[i][j]) {
                chk = 1;
            }
        }
    }
    if (chk == -1) {
        cout << num;
        return;
    }
    int div = cnt / 2;
    cout << "(";
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            sol(d + div * i, r + div * j, div);
        }
    }
    cout << ")";
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
             scanf("%1d",&arr[i][j]);
        }
    }
    sol(0, 0, n);
    cout << "\n";
}