[프로그래머스] 쿼드압축 후 개수 세기 - 분할 정복

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장.

 

쿼드압축 후 개수 세기

접근 방법

쿼드 압축은 2차원 배열을 4분할 했을 때 4면의 정보를 한 가지 표현으로 나타낸다. 문제에서 4면이 모두 같은 숫자인 경우 이를 해당 숫자 하나로 표현한다. 즉, 모두 같은 숫자를 가진 배열을 찾을 때 까지 주어진 배열을 4분할 한 뒤 각각에 대해 검사한다.

C++ 코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<vector<int>> cutInQuarter(vector<int> coord, vector<vector<int>> arr) {
    vector<int> row;
    vector<vector<int>> ret;
    for (int i = coord[0]; i < coord[1]; ++i) {
        for (int j = coord[2] ; j < coord[3]; ++j) 
            row.push_back(arr.at(i).at(j));
        ret.push_back(row);
        row.clear();
    }
    return ret;
}

vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer(2, 0); // {0, 0}

    // Base case: If all the numbers in the arr are same, update the answer vector and return.
    int n = arr[0][0];
    bool identical = true;
    for (const auto& row: arr) {
        for (const auto& e: row) 
            if (e != n) identical = false;
    }

    if (identical == true) {
        n == 0 ? answer[0] += 1 : answer[1] += 1;
        return answer;
    }

    // Different number exists.

    // Generate sub-array for each quarter of the arr and get into recursion.
    vector<vector<int>> quarterArr;
    int len = arr.size();
    vector<int> tmp(2, 0);
    // Coordinates for cutting array. {start row, end row, start column, end column}
    vector<int> coord(4);

    // Upper left.
    coord = {0, len / 2, 0, len / 2};
    quarterArr = cutInQuarter(coord, arr);
    tmp = solution(quarterArr);
    answer[0] += tmp[0]; answer[1] += tmp[1];

    // Upper right.
    coord = {0, len / 2, len / 2, len};
    quarterArr = cutInQuarter(coord, arr);
    tmp = solution(quarterArr);
    answer[0] += tmp[0]; answer[1] += tmp[1];

    // Lower left.
    coord = {len / 2, len, 0, len / 2};
    quarterArr = cutInQuarter(coord, arr);
    tmp = solution(quarterArr);
    answer[0] += tmp[0]; answer[1] += tmp[1];

    // Lower right.
    coord = {len / 2, len, len / 2, len};
    quarterArr = cutInQuarter(coord, arr);
    tmp = solution(quarterArr);
    answer[0] += tmp[0]; answer[1] += tmp[1];

    return answer;
}