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

 이 문제는 분할 정복을 이용해서 풀었다. 일단 이 문제에서 이차원 배열의 최대 크기는 1,024 * 1,024 = 1,048,576 이다. 그리고 범위 내 모든 수가 같지 않을 시, 즉 최악의 경우 0101...과 같은 형태일 경우 log4 (1,048,576) = 10이므로 시간 안에 풀 수 있다. 

 

 

 문제에서 주어진 순서가 있는데, 그 순서 그대로 짜면 정답이 나오는 쉬운 문제이다. 내가 고안한 수도코드는 다음과 같다.

1. 영역 안에서 모든 수를 카운트함
2-1. 만약 모든 수가 같다면
	그 같은 수에 대한 answer++
	함수 리턴
2-2. 그렇지 않다면
	정확히 4개의 영역으로 자른 것에 대한 재귀 호출 수행

위 수도코드를 그대로 구현하면 정답을 도출해낼 수 있다.

 

 

 

#include <string>
#include <vector>

using namespace std;

int result[2];

void solve(int startY, int startX, int size, vector<vector<int>>& arr) {
    // 1. count
    int first = arr[startY][startX];
    
    bool flag = true;
    for (int y = startY; y < startY + size; y++) {
        for (int x = startX; x < startX + size; x++) {
            if (first != arr[y][x]) {
                flag = false;
                break;
            }
        }
        if (!flag) {
            break;
        }
    }
    
    // 2-1. all same
    if (flag) {
        result[first]++;
        return;
    }
    
    // 2-2. not all same
    for (int y = startY; y < startY + size; y += size / 2) {
        for (int x = startX; x < startX + size; x += size / 2) {
            solve(y, x, size / 2, arr);
        }
    }
}

vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer;
    
    solve(0, 0, arr.size(), arr);
    
    answer.push_back(result[0]);
    answer.push_back(result[1]);
    
    return answer;
}