쿼드압축 후 개수 세기/C++

프로그래머스

문제 조건

• 정사각형 영역에서 영역 내부의 수가 모두 같은 값이라면 해당 영역을 수 하나로 압축시킨다.
• 그렇지 않다면 해당 영역을 같은 크기의 정사각형 영역 4개로 나누어 위의 조건을 수행한다.

풀이방법

1. 정사각형 영역을 모두 더했을 때 값이 0이라면 해당 영역 내부의 값들이 모두 0이므로 zero++

2. 정사각형 영역을 모두 더했을 때 값이 size*size라면 해당 영역 내부의 값들이 모두 1이므로 one++

3. 둘 다 아니라면 현재 영역을 같은 크기의 정사각형 영역 4개로 나누어 DFS 수행 

4. DFS가 종료된 후 answer 리턴

#include <string>
#include <vector>

using namespace std;

void DFS(vector<vector<int>>& arr, int x, int y, int size, int& zero, int& one) {
    if(size == 1) {
        if(arr[x][y] == 1) one++;
        else zero++;
        return;
    }
    
    int sum = 0;
    
    for(int i = 0; i < size; i++) {
        for(int j = 0; j < size; j++) 
            sum += arr[x + i][y + j];
    }
    
    if(sum == 0) {
        zero++;
        return;
    }
    else if(sum == size * size) {
        one++;
        return;
    }
    else {
        DFS(arr, x, y, size / 2, zero, one);
        DFS(arr, x, y + size / 2, size / 2, zero, one);
        DFS(arr, x + size / 2, y, size / 2, zero, one);
        DFS(arr, x + size / 2, y + size / 2, size / 2, zero, one);
    }
}

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