lv2 ) 쿼드압축 후 개수 세기[다시, 분할정복]

https://school.programmers.co.kr/learn/courses/30/lessons/68936?language=cpp

프로그래머스

 

내 풀이

#include <string>
#include <vector>
#include <iostream>
using namespace std;

//dfs
/*
1. dfs(완탐) 방식으로 정사각형의 width와 height 를 4분할한다.(for문 조건문)
2. isOneSet: 4분할을 통해 0과 1 둘 중 하나가 Full로 되있는지 아닌지 체크한다.
3. Full로 되있으면 더 이상 해당 lv의 브랜치에서 4분할로 쪼갤 필요 없다.(continue)
   Full로 되있으면 continue하기 전에 rt[0](0의 갯수), rt[1](1의 갯수) 중 하나에 +1 카운팅
4. Full이 아니면 재귀 이용해서 4분할로 쪼갠다.
5. 언제까지 재귀를 진행 할건지 : width 또는 height 반절까지의 lv
   행렬의 width 또는 height가 1, 2, 4, 8 즉 2의 n승만큼 증가하는 것이기에
   width 또는 height 의 반절까지의 lv에 접근해서 가지치기 한다. 
   해당 마지막 lv에 도착 할 때 2번(isOneSet)을 진행한다. 
   Full이 안되있으면 사용하는 CntZeroOne 구조체의 oneCnt와 zeroCnt의 누적갯수를
   rt[0], rt[1]에 누적해 더한다.
*/   

int rt[2]; // answer에 넣을 0, 1 값의 갯수 누적 배열

const int branch = 4;  // 4분할이기에 branch는 4개

//행렬에서 0의 갯수, 1의 갯수 카운팅
// isUse: CntZeroOne 구조체 사용여부(카운팅 사용여부)
// 0또는 1이 리프 노드 이전에 full로 되있을 경우 CntZeroOne 구조체는 사용할 필요가 없다.
// isOneSet메서드를 2번 사용하는데 
// 리프노드에서 한번, for문 recursion 들어가기 전에 한번 사용한다. 
struct CntZeroOne{
    int oneCnt;
    int zeroCnt;
    bool isUse;
};

//0 또는 1 Full여부체크, 0과 1 을 카운팅 할 시 CntZeroOne tmp 사용 (참조형태로 여러개의 갯수를 반환하게끔 진행)
int isOneSet(int stX, int stY, int enX, int enY,  
             const vector<vector<int>>& arr,
            CntZeroOne& tmp )
{
    bool isOne = false;
    bool isZero = false;
    for(int y = stY; y <= enY; ++y){
        for(int x = stX; x <= enX ; ++x){
            if(arr[y][x] == 1){
                isOne = true;
                if(tmp.isUse !=false){
                  tmp.oneCnt++;  
                }
                
            }
            else{
                isZero = true;
                if(tmp.isUse !=false){
                    tmp.zeroCnt++;
                }
            }
        }
    }
    if(isOne && isZero) return -1;
    if(isOne) return 1;
    if(isZero) return 0;
    return -1;
}
void recursion(int stL, int stH, int enL, int enH, int lv, const vector<vector<int>>& arr)
{
    // 리프노드에서 더 이상 재귀돌리지 않게 가지치기
    if(lv >= (arr.size()/2)){
        CntZeroOne tmp = {0,0, true}; // Full 여부 체크 및 0또는 1 갯수 체크
        int isRt = isOneSet(stL,stH,enL,enH,arr, tmp);
        if(isRt == -1){
            rt[0]+=tmp.zeroCnt;
            rt[1]+=tmp.oneCnt;
        }
        else if(isRt == 0){ // 모두 0인 경우
            rt[0] +=1;
        }
        else{ // 모두 1인 경우
            rt[1]+=1;
        }    
        return;
    }
    int rtTmp = -1; // Full 여부 체크 용도의 flag
    for(int idx = 0 ; idx < branch ; ++idx){
        CntZeroOne tmp = {0,0, false}; //단순 0또는 1의 full여부만체크하고자 3번째 인자는 false처리 (0또는 1 각각 카운팅 목적의 인자)

        if(idx == 0){ // 정사각형의 상좌 
             rtTmp = isOneSet(stL, stH, (((stL +1)  + (enL+1))/2) -1,(((stH + 1) + (enH + 1))/2) -1 ,arr , tmp);
            if(rtTmp == 1){
                rt[1]++;
                continue;
            }
            else if(rtTmp == 0){
                rt[0]++;
                continue;
            }
            recursion(stL, stH, (((stL +1)  + (enL+1))/2) -1,(((stH + 1) + (enH + 1))/2) -1 ,lv+1, arr);
        }
        if(idx == 1){ // 정사각형의 상우 
             rtTmp = isOneSet((((stL +1)  + (enL+1))/2), stH, enL,(((stH + 1) + (enH + 1))/2) -1 ,arr , tmp);
                        if(rtTmp == 1){
                rt[1]++;
                continue;
            }
            else if(rtTmp == 0){
                rt[0]++;
                continue;
            }
            recursion((((stL +1)  + (enL+1))/2), stH, enL,(((stH + 1) + (enH + 1))/2) -1 ,lv+1, arr);
           
        }
        if(idx == 2){ // 정사각형의 하좌 
              rtTmp =isOneSet(stL, (((stH + 1) + (enH + 1))/2), (((stL +1)  + (enL+1))/2) -1,enH ,arr , tmp);
            if(rtTmp == 1){
                rt[1]++;
                continue;
            }
            else if(rtTmp == 0){
               rt[0]++;
                continue;
            }
            recursion(stL, (((stH + 1) + (enH + 1))/2), (((stL +1)  + (enL+1))/2) -1,enH ,lv+1, arr);
        }
        if(idx == 3){  // 정사각형의 하우 
             rtTmp = isOneSet((((stL +1)  + (enL+1))/2), (((stH + 1) + (enH + 1))/2), enL, enH, arr , tmp);
            if(rtTmp == 1){
                rt[1]++;
                continue;
            }
            else if(rtTmp == 0){
                rt[0]++;
                continue;
            }
            recursion((((stL +1)  + (enL+1))/2), (((stH + 1) + (enH + 1))/2), enL, enH,lv+1, arr);
     
        }
    }
    
    return;
    
}
int initFullCheck(vector<vector<int>>arr){
    CntZeroOne tmp = {0,0,false};
    int rt = isOneSet(0,0,arr.size()-1, arr.size()-1, arr, tmp); // 사각형 전체 범위 체크
    if(rt == 1) return 1;
    if(rt==0)return 0;
    return -1;
}
vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer;
    //테스트케이스 10번: 정사각형의 초기값이 0 또는 1로 Full 된 경우
    int tmpRt = initFullCheck(arr);
    if(tmpRt == 1){
         answer.push_back(0);
           answer.push_back(1);
    }
    else if(tmpRt == 0){
         answer.push_back(0);
           answer.push_back(1);
    }
    else{ // 그렇지 않을 경우 정사각형 4분할 쪼개는 재귀 진행
            recursion(0,0,arr.size() - 1,arr.size() - 1, 0,arr);
            answer.push_back(rt[0]);
           answer.push_back(rt[1]);
    }

    return answer;
}

 

테스트케이스 10번 만 틀려서 힌트 얻고 initFullCheck 메서드 만들어서 진행.(처음에 모두 1 또는 0 인 경우)

 

dfs 방식으로 진행,

브랜치별 넓이와 높이를 4분할로 쪼갯다.

재귀를 돌리기 전 각 영역에 1 또는 0 이 해당 영역에 완전히 있는지 체크.

0과 1 둘다 같이 있으면 재귀를 계속 진행( arr 사이즈의 1/2 까지)

0과 1 중 하나라도 full로 있으면 더 이상 재귀를 돌리지 않고 rt[0] 또는 rt[1] 에 +1

dfs의 lv이 arr 사이즈의 1/2 까지 올 때 0과 1이 full 인 경우 또는 그렇지 않을 경우를 구분해서

full이면 해당 [0] 또는 [1] 인덱스에 +1

full이 아닐 경우 tmp.zeroCnt와 tmp.oneCnt 만큼 rt[0], [1] 에 각 누적해서 더함

 

 

TODO: 코드가 지저분하다, 타인 코드 참고하여 코드를 깔끔하게 만들기.

 

 

타인 코드

#include<string>
#include<vector>

using namespace std;

vector<vector<int>>MAP;

void DFS(int y, int x, int Size, vector<int>& answer) {
	if (Size == 1) {
		if (MAP[y][x] == 0) {
			answer[0]++;
		}
		else answer[1]++;
		return;
	}
	bool Zero, One;
	Zero = One = true;
	for (int dy = y; dy < y + Size; ++dy) {
		for (int dx = x; dx < x + Size; ++dx) {
			if (MAP[dy][dx] == 0) One = false;
			if (MAP[dy][dx] == 1) Zero = false;
		}
	}
	if (Zero) {
		answer[0]++;
		return;
	}
	if (One) {
		answer[1]++;
		return;
	}

	DFS(y, x, Size / 2, answer);
	DFS(y, x + Size / 2, Size / 2, answer);
	DFS(y + Size / 2, x, Size / 2, answer);
	DFS(y + Size / 2, x + Size / 2, Size / 2, answer);
}

vector<int>solution(vector<vector<int>>arr) {
	vector<int>answer(2, 0); // 1차원 벡터 2개 원소 0으로 초기화
	MAP = arr;
	DFS(0, 0, arr.size(), answer);
	return answer;
}