[C++] 프로그래머스 쿼드압축 후 개수 세기

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

프로그래머스

풀이

대표적인 분할정복 문제 중 하나인 쿼드트리 압축과 관련된 문제입니다.

해당 문제에서는 쿼드 트리 압축 후 0과 1의 개수를 세어 반환해야 합니다.

 

분할 정복은 일반적으로 재귀함수를 사용해 구현할 수 있습니다. 해당 문제에서는 재귀 함수 compress를 구현하여 전역변수 answer를 처리하여 정답을 반환하였습니다.

 

 compress는 쿼드트리 arr, 검색해야 하는 크기 size, 탐색을 시작해야하는 행열 row, col를 매개변수로 받으면서, 가장 작은 정사각형으로 나눠진 기저 조건, 압축 가능한 상황, 압축 불가능한 상황을 처리하는 코드로 나눠 구현할 수 있습니다.

 

1. size가 1인 경우가 가장 작은 단위로 압축된 형태이며, 이 때는 바로 answer를 처리하고 return 해줍니다.

 

2. 기저조건이 아니라면, 현재 size의 정사각형이 모든 같은 숫자로 이뤄졌는지 판단합니다. can_compress 변수를 사용해 압축 가능하다면 answer를 처리해주고 return하여 해당 정사각형 영역의 압축을 종료합니다.

 

3. 압축이 불가능한 경우 다시 4구역으로 나눠 compress 함수를 호출해 재귀적으로 압축을 진행합니다.

 

 

#include <string>
#include <vector>

using namespace std;

vector<int> answer = {0, 0};

void compress(vector<vector<int>> &arr, int size, int row, int col)
{
    // 기저 조건
    if (size == 1) {
        if (arr[row][col] == 0)
            answer[0]++;
        else 
            answer[1]++;
        
        return;
    }
    // 현재 정사각형이 같은 숫자인지 확인
    int head = arr[row][col];
    bool can_compress = true;
    for (int i = row; i < row+size; i++) {
        for (int j = col; j < col+size; j++) {
            if (head != arr[i][j]) {
                can_compress = false;
                break;
            }
        }
    }
    // 압축 가능
    if (can_compress) {
        answer[head]++;
        return;
    }
    
    // n크기 정사각형을 n/2 4 조각 분할 & 시작 위치 전달
    compress(arr, size/2, row, col);
    compress(arr, size/2, row, col + size/2);
    compress(arr, size/2, row + size/2, col);
    compress(arr, size/2, row + size/2, col + size/2);
    
}

vector<int> solution(vector<vector<int>> arr) {
    
    int n = arr.size();
    compress(arr, n, 0, 0);
    return answer;
}