[프로그래머스] 월간 코드 챌린지 - 쿼드압축 후 개수 세기

programmers.co.kr/learn/courses/30/lessons/68936

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

 

문제 설명

0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.

1. 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
2. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
3. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.

arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1, 2, 4, 8, ..., 1024 중 하나입니다.
  • arr의 각 행의 길이는 arr의 행의 개수와 같습니다. 즉, arr은 정사각형 배열입니다.
  • arr의 각 행에 있는 모든 값은 0 또는 1 입니다.

---

입출력 예

arrresult

[[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]]	[4,9]
[[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]]	[10,15]

---

입출력 예 설명

입출력 예 #1

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.

• 

• 최종 압축 결과에 0이 4개, 1이 9개 있으므로, [4,9]를 return 해야 합니다.

입출력 예 #2

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.

• 

• 최종 압축 결과에 0이 10개, 1이 15개 있으므로, [10,15]를 return 해야 합니다.

 

풀이방법

재귀호출과 완전탐색 알고리즘을 이용해서 풀었다.

 

1) 

#include <string>
#include <vector>
 
using namespace std;
 
int one = 0, zero = 0;
int map[1025][1025];
void compress(int x1, int x2, int y1, int y2){
    int count = 0;
    for(int i=x1; i<x2; i++){
        for(int j=y1; j<y2; j++){
            if(map[i][j] == 1){
                count ++;
            }
        }
    }
    
    if((x2-x1)*(y2-y1) == count) one++;
    else if(count == 0) zero ++;
    else{
        int a = (x1 + x2)/2;
        int b = (y1 + y2)/2;
        compress(x1, a, y1, b);
        compress(x1, a, b, y2);
        compress(a, x2, y1, b);
        compress(a, x2, b, y2);
    }
}
vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer;
    
    int n = arr.size();
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            map[i][j] = arr[i][j];
        }
    }
    
    compress(0, n, 0, n);
    
    answer.push_back(zero);
    answer.push_back(one);
    
    return answer;
}

2) 

#include <string>
#include <vector>
 
using namespace std;
 
vector<vector<int>> map;
void compress(int x, int y, int size, vector<int> &answer){
    if(size == 1){
        if(map[x][y]==0) {
            answer[0]++;
            return;
        }
        else {
            answer[1]++;
            return;
        }
    }
    bool one = true, zero = true;
    for(int i=x; i<x+size; i++){
        for(int j=y; j<y+size; j++){
            if(map[i][j]==0) one = false;
            if(map[i][j]==1) zero = false;
        }
    }
    if(zero){
        answer[0]++;
        return;
    }
    if(one){
        answer[1]++;
        return;
    }
    
    compress(x, y, size/2, answer);
    compress(x, y+size/2, size/2, answer);
    compress(x+size/2, y, size/2, answer);
    compress(x+size/2, y+size/2, size/2, answer);
    
}
vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer(2, 0); //사이즈가 2인 벡터 0으로 초기화
    map = arr;
    int n = arr.size();
    compress(0, 0, n, answer);
    return answer;
}