프로그래머스[Lv.2] - 쿼드압축 후 개수 세기

 

문제 설명

0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.

• 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
• 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
• 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.

arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

---

 

 

 

 

 

 

제한 사항

• arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1, 2, 4, 8, ..., 1024 중 하나입니다.
  • arr의 각 행의 길이는 arr의 행의 개수와 같습니다. 즉, arr은 정사각형 배열입니다.
  • arr의 각 행에 있는 모든 값은 0 또는 1 입니다.

---

 

 

 

 

 

 

풀이

처음 문제를 읽었을 때는 고민했지만, 천천히 생각해 보니 동일한 작업을 사이즈만 줄여가며 실행한다는 것을 알 수 있었다.

반복되는 작업은 현재 사이즈에서 체크했을 때, 실패한다면 실행하는 것이다.

즉, 재귀를 이용하여 가능여부를 확인한 뒤 만약 불가능하다면 4개의 구역으로 나누어 다시 진행하면 된다.

4개의 구역으로 나눌 때는 size/2만큼 y, x를 이동시키면 된다.

---

 

 

 

 

 

전체 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

bool CheckRegion(vector<vector<int>>& arr, int y, int x, int size)
{
    int target = arr[y][x];
    
    for(int i = y; i < y+size; i++)
    {
        for(int j = x; j < x+size; j++)
        {
            if(target != arr[i][j]) return false;
        }
    }
    
    return true;
}

void Compress(vector<int>& answer, vector<vector<int>>& arr, int y, int x, int size)
{
    if(y < 0 || y >= arr.size() || x < 0 || x >= arr[0].size()) return;
    
    if(CheckRegion(arr, y, x, size))
    {
        answer[arr[y][x]]++;
        return;
    }
    
    //4개로 분리
    int half = size/2;
    if(half == 0) return;
    
    Compress(answer, arr, y, x, half);
    Compress(answer, arr, y, x+half, half);
    Compress(answer, arr, y+half, x, half);
    Compress(answer, arr, y+half, x+half, half);
}

vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer;
    
    answer.push_back(0);
    answer.push_back(0);
    
    Compress(answer, arr, 0, 0, arr.size());
    
    return answer;
}

---