(C++) - 프로그래머스(월간코드챌린지) : 쿼드압축 후 개수 세기

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

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

재귀함수를 구현하는 문제였습니다.

 

풀이방법

1. 부분 정사각형의 면적이 모두 같은 영역인지 확인합니다.

2. 정사각형의 영역이 모두 같은 수(0,1)로 되어 있다면 압축이 가능합니다. 반대의 경우는 압축이 불가능하므로 4개의 영역으로 쪼갭니다.

3. 더이상 영역을 나눌 수 없을 때 영역의 개수를 갱신합니다.

* 재귀함수로 변수를 넘길 때 얕은 복사로 메모리를 따로 파는 낭비를 피함으로써 시간초과를 해결합니다.

Code

#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector <int> a(2,0);
bool needDivision(vector<vector<int>> &arr, int i,int j ,int size) {
    int source = arr[i][j];
    for(int x = i; x<i+size; x++){
        for(int y = j; y < j + size; y++){
            if(source!=arr[x][y]) return 1;
        }
    }
    return 0;
}
void quadTree(vector <vector<int>> &arr,int i,int j,int size){
    if(needDivision(arr,i,j,size)){
        quadTree(arr,i + size/2, j + size/2,size/2);
        quadTree(arr,i, j + size/2,size/2);
        quadTree(arr,i + size/2, j ,size/2);
        quadTree(arr,i, j,size/2);
    } else{
        if(arr[i][j]==1) a[1]++;
        else a[0]++;
        return;
    }
}

vector<int> solution(vector<vector<int>> arr) {
    int size = arr.size();
    quadTree(arr,0,0,size);
    return a;
}