[프로그래머스][level2] 쿼드압축 후 개수 세기 (C++)

https://programmers.co.kr/learn/courses/30/lessons/68936

코딩테스트 연습 - 쿼드압축 후 개수 세기

 

 

[난이도] level2
[유형] 분할정복

[풀이]
정사각형의 수가 모두 같지 않다면 4개로 분할된 정사각형을 다시 검사하도록
재귀함수를 호출해주고 모두 같다면 0,1인지에 따라 개수를 1개 더해줍니다.

 

#include <string>
#include <vector>
using namespace std;
vector<int> answer(2);
vector<vector<int>> arr;
int same(int y,int x,int n){
    int t = arr[y][x];
    for(int i=y;i<y+n;i++)
        for(int j=x;j<x+n;j++)
            if(t!=arr[i][j]) return -1;
    return t;
}
void sol(int y,int x,int n){
    int ret = same(y,x,n);
    if(ret!=-1){
        answer[ret]++;
        return;
    }    
    int b = n/2;
    sol(y,x,b);
    sol(y+b,x,b);
    sol(y,x+b,b);
    sol(y+b,x+b,b);
}

vector<int> solution(vector<vector<int>> _arr) {
    arr=_arr;
    sol(0,0,arr.size());
    return answer;
}

 

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/쿼드압축 후 개수 세기.cpp