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

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

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

[해결방법]

분할정복

분할한 맵의 크기가 1일 때까지 분할한다.

분할한 맵의 인자들이 모두 같은 수인지 확인하는 과정이 필요하다.

#include <string>
#include <iostream>
#include <vector>

using namespace std;
vector <vector <int>> map;
int one_cnt, zero_cnt;

void divide(int cy, int cx, int size) {
    if(size == 1) {
        if(map[cy][cx] == 0)
            zero_cnt++;
        else if(map[cy][cx] == 1)
            one_cnt++;
        return;
    }
    // compare
    bool same = true;
    int no = map[cy][cx];
    for(int i=0; i<size; i++) {
        for(int j=0; j<size; j++) {
            int ny = cy + i;
            int nx = cx + j;
            if(no != map[ny][nx]) {
                same = false;
                break;
            }
        }
    }
    if(same) {
        if(no == 1)
            one_cnt++;
        else if(no == 0)
            zero_cnt++;
        return;
    }
    divide(cy, cx, size/2);
    divide(cy, cx+(size/2), size/2);
    divide(cy+(size/2), cx, size/2);
    divide(cy+(size/2), cx+(size/2), size/2);
}

vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer;
    map = arr;
    
    divide(0, 0, map.size());
    
    answer.push_back(zero_cnt);
    answer.push_back(one_cnt);
    
    return answer;
}