26. 쿼드압축 후 개수 세기 Lv.3 : 월간 코드챌린지 시즌1 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/68936

프로그래머스

 

*코드

#include <string>
#include <vector>

using namespace std;

int zero,one;

void dfs(int y,int x,int size,vector<vector<int>> &arr){
    int cur = arr[y][x]; // 맨 처음 값
    
    bool equals=true; // 현재 사각형이 모두 같은수라면 해당 dfs종료한다.
    
    // 사각형 내부가 전부 같은 수인지 판별
    for(int i = y ; i < y + size ; i++){
        for(int j = x ; j < x+size ; j++){
            if(cur != arr[i][j]){
                equals = false;
                break;
            }
        }
    }

    // 모두 같은 수라면 0 또는 1 의 개수 증가 후 
    // 재귀 호출 하지 않고 바로 return
    // cur 이 0이라면 그 사각형이 0으로 통일된거라 zero++ 아니면 one++ 
    if(equals){
        cur==0 ? zero++ : one++ ;
        return;
    }
    // 현재 사각형을 4등분하여 재귀함수 호출
    dfs(y,x,size/2,arr);
    dfs(y,x+size/2,size/2,arr);
    dfs(y+size/2,x,size/2,arr);
    dfs(y+size/2,x+size/2,size/2,arr);

}

vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer;

    dfs(0,0, arr.size() ,arr);
    
    answer.assign({zero,one});
    return answer;
}

 

*해설

 일단 항상 정사각형을 4 등분한다는 것은 다음과 같이 생각할 수 있다. 한 변의 길이를 size라고 표현한다면

(y, x, size) 이 양식 대로 할때

 

사각형 1 : (y,x,size/2 )

사각형 2 : (y,x+size/2, size/2 )

사각형 3 : (y+size/2,x, size/2 )

사각형 4 : (y+size/2,x, size/2 )

 

이렇게 된다.

 

여기 까지 구했으면 어렵지가 않다. 사각형 내부 수가 하나로 통일 될때까지 무한 반복만 하면될 뿐.

그리고 하나로 통일 될 경우 그 통일 된 것이 0인지 1인지에 따라 zero나 one 변수의 값을 한 개씩 증가시키면 될 것이다.