[프로그래머스] 쿼드압축후개수세기

문제 요약

쿼드 압축이 끝난 후의 1과 0의 개수를 세어봅시다!

쿼드압축방법
if 정사각형 영역인 S가 같은 숫자로 구성돼 있다?
=>하나의 숫자가 S를 대표함
else => S를 4개의 정사각형으로 쪼개 쿼드압축이 가능한지 확인한다.

아이디어

재귀함수를 만들어줬다.
base 조건은 영역 사이즈가 1일 때로 이땐 그 영역 값의 개수를 올려줬다.
합칠 수 있는지 검사는 사각형 최대사이즈가 10^3이라서 그냥 영역 사이즈만큼 돌면서 했다. 프로그래머스 가장 큰 사각형 찾기 문제에서처럼 각 시작점마다 DP적으로 같은 값을 가지는 정사각형 영역을 찾을 수 있겠다는 생각도 든다.

코드 c++

#include <string>
#include <vector>
#include<iostream>
using namespace std;
int ns[]={0,0};
void check(vector<vector<int>> &arr,int si, int sj, int sz){
    int val = arr[si][sj];
    if(sz==1){
        ns[val]++;
        return;
    }
    bool mergable =true;
    for(int i = si;i<si+sz;i++){
        for(int j = sj;j<sj+sz;j++){
            if(arr[i][j]!= val){
                mergable = false;
            }
        }
    }
    if(mergable){
        ns[val]++;
        //cout<<si<<" "<<sj<<" "<<val<<" "<<sz<<endl;
    }
    else{
        sz = sz/2;
        check(arr, si,sj,sz);
        check(arr, si,sj+sz, sz);
        check(arr, si+sz,sj, sz);
        check(arr, si+sz,sj+sz,sz);
    }
}


vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer;
    check(arr, 0,0,arr.size());
    answer.push_back(ns[0]);
    answer.push_back(ns[1]);
    return answer;
}

코드 python

s_num = [0,0]
def div(arr, si,sj,sz):
    seed = arr[si][sj]
    pure = True
    for i in range(si, si+sz):
        for j in range(sj, sj+sz):
            if(arr[i][j]!=arr[si][sj]):
                pure = False
    if pure:
        s_num[seed]+=1
    else:
        hsz = sz//2
        div(arr, si, sj, hsz)
        div(arr, si, sj+hsz, hsz)
        div(arr, si+hsz, sj,hsz)
        div(arr, si+hsz,sj+hsz, hsz)

def solution(arr):
    answer = []
    div(arr, 0,0,len(arr))
    answer= s_num
    return answer