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

[문제]

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

 

[풀이]

 

answer size는 2로 초기화한다. [0]은 0의 갯수, [1]은 1의 갯수를 담을 것이다.isCompressible() 함수로는 해당 영역이 모두 같은지 확인하는 함수로, arr과 시작위치 y, x, 검사할 정사각형 한 변의 길이 size를 전달한다. 예를들어

 

arr = {1, 1}. {1, 1};

 

이 입력이라면, isCompressible(arr, 0, 0, 2)를 전달하고 true를 반환받는다.

 

QuadTree() 함수는 재귀 형식이다. 해당 구역이 압축 가능한 경우는 그 숫자 하나만 카운트하고 리턴하고, 압축이 불가능한 경우는 네 개로 나눠서 다시 QuadTree 재귀 호출을 실시한다.

#include <vector>

using namespace std;

vector<int> answer(2); // 0의 개수, 1의 개수

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

void QuadTree(const vector<vector<int>>& arr, int y, int x, int size)
{
    if (isCompressible(arr, y, x, size))
    {
        answer[arr[y][x]]++;
        return;
    }

    int half = size / 2;
    QuadTree(arr, y, x, half);                     // 왼쪽 위
    QuadTree(arr, y, x + half, half);              // 오른쪽 위
    QuadTree(arr, y + half, x, half);              // 왼쪽 아래
    QuadTree(arr, y + half, x + half, half);       // 오른쪽 아래
}

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