[DFS, 난이도 중] 프로그래머즈, 쿼드압축 후 개수 세기

 

전체 영역을 4분할 한뒤 분할 영역 안의 요소가 모두 같을 경우에는 압축하고, 그렇지 않을 경우에는 분할 영역을 다시 4분할해가는 식으로 진행한다.

이 방식으로 모두 압축했을 때 남아있는 0,1의 개수를 계산하면 되는 문제이다.

자세한 설명은 맨 아래 첨부한 코드의 주석에 달아놓았다.

dfs함수를 수행하기 전에 전체 영역에 대해 요소가 모두 같은지 여부를 알아내야 한다.

그 이유는 dfs함수에서는 영역을 4분할 하고 계산하기 때문에, 전체 영역을 바로 넣어버리면 전체 영역에 대해 요소가 모두 같더라도 강제로 4분할이 되어 버린다.

이러한 과정이 없다면, [[1,1],[1,1]] 이 입력으로 주어지더라도 출력값은 [0,1]이 아닌 [0,4]가 되어버릴 것이다.

 

테스트 케이스 16개 모두 통과

 

#include <vector>
using namespace std;
vector<vector<int>> arr;
int a[2];

void dfs(int x, int y, int m) { //시작좌표(x,y), 영역의 한변의 길이
    //2,1,3,4분면 순으로 분할정복
    int phasex[4] = {x,x,x+m/2,x+m/2};
    int phasey[4] = {y,y+m/2,y,y+m/2};
    int base; //기준: 0 or 1
    bool stop; //분할정복을 더 깊이 진행해야하는지 여부
    for(int p=0;p<4;p++){
        base=arr[phasex[p]][phasey[p]];
        stop=true;
        for(int i=phasex[p];i<phasex[p]+m/2;i++){
            for(int j=phasey[p];j<phasey[p]+m/2;j++){
                if(arr[i][j]!=base) stop=false;
            }
        }
        if(stop) a[base]++;
        else dfs(phasex[p],phasey[p],m/2);
    }
}
vector<int> solution(vector<vector<int>> _arr) {
    vector<int> answer;
    arr=_arr;
    //쿼드 트리의 모든 영역이 같은 수 일 경우 고려
    int base=arr[0][0];
    bool allsame=true;
    for(int i=0;i<arr.size();i++){
        for(int j=0;j<arr.size();j++){
            if(arr[i][j]!=base) allsame=false;
        }
    }
    if(allsame){
        a[base]++;
        answer.push_back(a[0]);
        answer.push_back(a[1]);
        return answer;
    }
    //그렇지 않을 경우 dfs수행
    dfs(0,0,arr.size());
    answer.push_back(a[0]);
    answer.push_back(a[1]);
    return answer;
}