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

문제 설명

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 입니다.

---

입출력 예

 

 

입출력 예 설명

입출력 예 #1

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

• 

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

입출력 예 #2

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



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

 

풀이

큐와 튜플을 활용했다.

각 영역에 대해 4등분하고 압축완료 여부를 판단한다.

압축이 됐거나 원소가 1개만 남았다면 그 값을 answer에 추가한다.

압축이 되지 않았다면 서로 다른 원소가 존재하기 때문에 해당 영역에 대해 다시 4등분으로 쪼개 반복한다.

 

#include <string>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer(2);
    queue< tuple<int,int,int,int> > q;
    
    q.push( make_tuple(0, arr.size(), 0, arr.size()) );
    
    while(!q.empty()){
        int start_x = get<0>(q.front());
        int end_x = get<1>(q.front());
        int start_y = get<2>(q.front());
        int end_y = get<3>(q.front());
        
        q.pop();
        
        bool common = true;
        for(int i=start_x; i<end_x; i++){
            for(int j=start_y; j<end_y; j++){
                if(arr[start_x][start_y] != arr[i][j]) common = false;
            }
        }
        
        if(common){
            if(arr[start_x][start_y]) ++answer[1];
            else ++answer[0];
        }else{
            q.push( make_tuple(start_x, (start_x + end_x)/2, start_y, (start_y +end_y)/2) );
            q.push( make_tuple(start_x, (start_x + end_x)/2, (start_y +end_y)/2, end_y) );
            q.push( make_tuple((start_x + end_x)/2, end_x, start_y, (start_y +end_y)/2) );
            q.push( make_tuple((start_x + end_x)/2, end_x, (start_y +end_y)/2, end_y) );
        }
    }
    
    return answer;
}