[프로그래머스 lv2] 쿼드 압축 후 개수 세기 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

주어진 정사각형의 한변의 길이를 n이라 할 때, n x n 정사각형을 4개로 나누어가며 압축하는 문제이다.

정사각형의 한 변의 길이는 n -> n/2 -> n/4 -> ... -> 1 이 되는데, 해당 과정을 재귀로 처리할 수 있다.

 

func(int x, int y, int n)은 왼쪽 위 꼭짓점이 (x, y)이고 한변의 길이가 n인 정사각형에 대하여, 쿼드 압축 결과를 구하는 함수이다.

만약, 해당 정사각형이 모두 같은 수로 이루어져있다면 그 수의 개수를 1 증가시킨다.

만약, 해당 정사각형이 모두 같은 수로 이루어져있지않다면, 한변의 길이가 n/2인 4개의 정사각형으로 나누어 재귀적으로 쿼드 압축 결과를 구한다.

4개 정사각형의 각 꼭직점은 (x, y), (x, y+n/2), (x+n/2, y), (x+n/2, y+n/2)가 된다.

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

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

void func(int x, int y, int n, vector<int>& cnt, const vector<vector<int>>& arr) {
    
    if (check(x, y, n, arr)) {
        cnt[arr[x][y]]++;
        return ;
    }
    
    func(x, y, n/2, cnt, arr);
    func(x, y+n/2, n/2, cnt, arr);
    func(x+n/2, y, n/2, cnt, arr);
    func(x+n/2, y+n/2, n/2, cnt, arr);
}

vector<int> solution(vector<vector<int>> arr) {
    
    int n = arr.size();
    vector<int> cnt(2, 0);
    func(0, 0, n, cnt, arr);
    return cnt;
}