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

1. 문제

programmers.co.kr/learn/courses/30/lessons/68936?language=cpp

코딩테스트 연습 - 쿼드압축 후 개수 세기

2. 풀이

먼저 재귀로 풀어야겠다는 생각이 들었다. 하지만 어디서부터 어디까지 반복을 해야하지?

라는 생각이 들었고 결과적으로 각 좌표의 시작점마다 재귀함수로 각 범위별로 모두 0인지, 모두 1인지, 둘다 아닌지 이 3가지 경우를 판단해야한다.

 

처음의 경우 (0,0), (0, n), (n,0), (n,n) 의 좌표로 각 범위의 시작 좌표가 된다. (왼쪽 맨위 좌표를 시작 좌표로 지정.)

이때 n의 크기를 2로 나누어 더 줄어들게 된다면 (0,0), (n/2,0), (0, n/2), (n/2, n/2) 의 좌표로 범위의 시작점이 된다.

 

이를 일반화하면

(y, x), (y, x+n) (y+n, x) (y+n, x+n)의 좌표로 각 범위를 탐색한다.

 

모두 0으로 구성되어 있으면 num_of_zero 증가, 재귀 종료

모두 1로 구성되어 있으면 num_of_one 증가, 재귀 종료

 

n의 크기를 2로 나누어서 재귀 반복

 

3. 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
/*
한 변의 길이가 2가 될때까지 압축
answer = [0의개수, 1의개수]
(0,0)
(0, 0 + n)
(0 + n, 0)
(n, n)
*/
using namespace std;

int num_of_one = 0;
int num_of_zero = 0;

void compression(int y, int x, int n, vector<vector<int>> &arr){
    bool one = true;
    bool zero = true;
    for(int i=y; i<y + n; i++){
        for(int j=x; j<x + n; j++){
            if(arr[i][j] == 0)
                one = false;
            if(arr[i][j] == 1)
                zero = false;
        }
    }
    if(zero == true){
        num_of_zero++;
        return;
    }
    if(one == true){
        num_of_one++;
        return;
    }
    compression(y, x, n/2, arr);
    compression(y+n/2, x, n/2, arr);
    compression(y, x+n/2, n/2, arr);
    compression(y+n/2, x+n/2, n/2, arr);
    
}

vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer;
    int size = arr.size();
    
    compression(0, 0, size, arr);
    
    answer.push_back(num_of_zero);
    answer.push_back(num_of_one);
    return answer;
}