프로그래머스 - 쿼드 압축 후 개수 세기(C++ / Java)

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

프로그래머스

 

코딩테스트에도 1~2번 정도로 나올 수 있는 재귀문제이다.

 

 

위의 배열이 들어왔을 때 만약 모든 원소가 0 or 1 이 아니라면 4부분으로 나누어 재귀에 들어가야한다. 이 재귀를 할 범위를 찾는 것이 은근히 까다로운데, 여기서 정리하고 가도록 하자.

 

1. 먼저 기준점을 잡는다. 보통 왼쪽 상단이 편리하다.

2. 그리고 지금 사각형의 한 변의 길이가 필요하다. 왼쪽 상단부터 변의 길이만큼 반복해야하기 때문이다.

 

위 식을 재귀함수로 써보면  다음과 같다.

 

fuction(int x, int y, int size){
	if(check) // 0 or 1 이 아니면
    
    int nextSize = size / 2;
    
    fuction(x, y, nextSize) // 1번
    fuction(x + nextSize, y, nextSize) // 2번
    fuction(x, y + nextSize, nextSize) // 3번
    fuction(x + nextSize, y + nextSize, nextSize) // 4번
}

 

뭔가 쉬운데 생각을 잘못하면 쓸대없이 시간을 많이쓸수있는 문제이다. 

 

C++

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> vec;
vector<int> answer(2, 0);

void rec(int x, int y, int s){
    int v = vec[x][y];
    bool flag = false;
    for(int i = x; i < x + s; i++){
        for(int j = y; j < y + s; j++){
            if(v != vec[i][j]){
                flag = true;
            }
        }
    }
    
    if(flag){
        int k = s / 2;
        rec(x ,y, k);
        rec(x + k, y + k, k);
        rec(x + k, y, k);
        rec(x, y + k, k);
    }else{
        answer[v]++;
    }
}

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

 

Java

 

class Solution {
    static int[] answer = {0, 0};
    static int[][] vec;
    public int[] solution(int[][] arr) {
        vec = arr;
        
        rec(0,0,arr.length);
        
        return answer;
    }
    
    static void rec(int x, int y, int s){
        int st = vec[x][y];
        boolean flag = false;
        
        for(int i = x; i < x + s; i++){
            for(int j = y; j < y + s; j++){
                if(vec[i][j] != st) {
                    flag = true;
                }
            }
        }
        
        if(flag){
            rec(x, y, s / 2);
            rec(x, y + s / 2, s / 2);
            rec(x + s / 2, y, s / 2);
            rec(x + s / 2, y + s / 2, s / 2);
        }else{
            answer[st]++;
        }
    }
}