프로그래머스 - 쿼드압축 후 세기

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

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

 

백준 2630 색종이 만들기 (https://www.acmicpc.net/problem/2630)  문제와 비슷한 문제다.

1. 정사각형 구역을 분할하는 경우는 주어진 정사각형의 값들이 서로 다른 케이스가 존재할때이다.

(그 외에 전부 1이거나, 전부 0 인 경우 분할하지 않는다)

2. 정사각형 구역 분할을 위한 필요요소는

(1). 분할 각 구역의 탐색 시작 좌표, (2). 현재 구역의 정사각형 한변의 길이로 처리한다.

3. 0 과 1의 갯수를 갖고 있는 전역변수 int cnt[2] 를 선언해서, 해당 구역이 모두 같은 0 이거나 1일때 카운팅한다.

 

- c++

 

#include <vector>
 
using namespace std;
 
int cnt[2];
 
void divide_and_conquer(vector<vector<int>>& arr, int y, int x, int k) {
    bool flag = true;
    int base = arr[y][x];
    for (int i = y; i < y + k; ++i) {
        for (int j = x; j < x + k; ++j) {
            if (base != arr[i][j]) flag = false;
        }
    }
 
    if (flag)
        cnt[base]++;
    else {
        divide_and_conquer(arr, y, x, k / 2);
        divide_and_conquer(arr, y, x + k / 2, k / 2);
        divide_and_conquer(arr, y + k / 2, x, k / 2);
        divide_and_conquer(arr, y + k / 2, x + k / 2, k / 2);
    }
}
 
vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer;
    divide_and_conquer(arr, 0, 0, arr.size());
    answer.resize(2);
    answer[0] = cnt[0];
    answer[1] = cnt[1];
    return answer;
}