문제 68936. 쿼드압축 후 개수 세기

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/68936

프로그래머스

 

 

난이도 :  Lv.2

 

문제 요약 설명

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

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

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

입력

• arr

입력 제한

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

입력 예제

// input
[[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] // arr

// ans
[4,9]

 

풀이 방식

이 문제는 이미지를 압축할 때 사용하는 방식 중에 하나로 보인다. 압축 방식은 문제 설명에 적혀있는 것처럼 특정 영역에 있는 모든 비트가 동일하면 해당 비트 1개로 압축시킨다. 즉, 아래 사진처럼 압축한다(입력 예제 활용)

0은 4개, 1은 9개이므로 정답은 [4, 9]가 된다

 

위 예시에서는 한 번만 압축되었지만, 0또는 1로만 이루어진 영역이 더 있었다면 여러 번 압축되었을 것이다. 그렇다면 이 문제는 어떻게 풀어야할까?

필자는 분할정복 알고리즘(Divide and conquer)을 사용했다. 가장 작은 쿼드 영역(2*2)부터 압축해서 4*4, 8*8, 16*16...2^n*2^n 순으로 순서대로 압축하면 결과가 나올 것이라고 판단했기 때문이다. 입력은 항상 정사각형으로 주어지므로 가로와 세로 길이가 달라서 고려해야하는 추가적인 상황또한 없기에 그대로 재귀를 통해 분할정복을 하면된다. 

 

본격적인 알고리즘 내부 구현

우선, 분할정복 알고리즘을 사용하려면 분할이 되는 코드를 짜야한다. 한 번 분할할때 생기는 영역을 총 4개로 각 영역에 숫자를 붙이면 아래 그림과 같다.

입력은 항상 정사각형으로 주어지므로, 각 영역은 현재 진입한 정사각형의 크기가 N이라고 했을 때, 다음과 같은 위치에서 시작한다. (시작 위치를 x, y라고 가정한다.)

• 1번 영역: (x, y)
• 2번 영역: (x, y+N/2)
• 3번 영역: (x+N/2, y)
• 4번 영역: (x+N/2 , y+N/2)

따라서, 위처럼 분할된 정사각형의 시작 위치를 구한 다음, 다시 분할 정복을 하기 위해 재귀적으로 분할 정복 알고리즘에 들어가면 되는데 이를 아래와 같이 구현했다.

int area_x[AREA] = {0, 0, arr_size/2, arr_size/2}; // 분할한 4개의 각 영역 x축 offset
int area_y[AREA] = {0, arr_size/2, 0, arr_size/2}; // 분할한 4개의 각 영역 y축 offset

vector<int> v_zero, v_one;

// 분할한 각 정사각형에서 다시 분할 정복 알고리즘을 호출하고, 그 결과를 저장한다.
for(int i = 0; i < AREA; i++){
    int min_nx = min_x + area_x[i];
    int min_ny = min_y + area_y[i];
    p = dnc(min_nx, min_ny, arr_size/2);	// 참고로 dnc는 divide and conquer의 약자이다

    v_zero.push_back(p.first);
    v_one.push_back(p.second);
}

 

이렇게 재귀적으로 분할 정복 알고리즘을 실행한 다음, 정복이 마무리되면 배열인 v_zero, v_one에 정복된 4개의 영역의 0비트의 개수, 1비트의 총 개수가 저장되게 된다. 이를 통해 현재 진입한 정사각형의 정복한 결과를 구해야한다.

 

정복한 결과를 구하는 방법은 간단하다. v_zero, v_one는 항상 4의 길이를 가지며(항상 4개의 영역으로 분할하기 때문) 각각 해당 영역의 비트 개수를 의미하기 때문에, 각 영역의 정복 결과가 1이 아니라면 압축되지 못했다는 것이므로 1이 아닌 경우가 4번 중 1번이라도 발생하면 압축 풀가 판정(is_merged_xxx = false)을 낸다. 만약, 한 번도 압축 불가 판정이 나지 않았다면 압축이 가능하므로, 정복 결과를 비트 개수 1개로 한다. 이러한 압축은 2가지 방법(0 또는 1)으로 할 수 있으니 각각 따로 구한다.

 

압축 시도후 결과를 구하는 코드

bool ismerged_zero = true;
for(int elem : v_zero){
    if(elem != 1){
        ismerged_zero = false;
    }
    ans_p.first += elem;
}

bool ismerged_one = true;
for(int elem : v_one){
    if(elem != 1){
        ismerged_one = false;
    }
    ans_p.second += elem;
}
if(ismerged_zero && ans_p.second == 0) ans_p.first = 1;
if(ismerged_one && ans_p.first == 0) ans_p.second = 1;

 

이렇게 구한 결과물을 2개(압축 시도 후 0의 개수, 압축 시도후 1의 개수)를 분할 정복 알고리즘의 반환값으로 넣어주면 코드는 완성이 된다. 마지막으로 가장 처음 분할 정복 알고리즘의 반환값을 저장해 answer변수에 넣어주면 정답이 된다.

 

 

정답 코드 

 

#include <string>
#include <vector>
#include <iostream>
#include <utility>

#define AREA 4

using namespace std;
vector<vector<int>> arr_global;

pair<int, int> dnc(int min_x, int min_y, int arr_size){
    
    pair<int, int> p;
    pair<int, int> ans_p = make_pair(0, 0);
    
    if(arr_size == 1){
        ans_p = arr_global[min_x][min_y] ? make_pair(0, 1) : make_pair(1, 0);
        return ans_p;
    }
    
    int area_x[AREA] = {0, 0, arr_size/2, arr_size/2};
    int area_y[AREA] = {0, arr_size/2, 0, arr_size/2};
    
    vector<int> v_zero, v_one;
    for(int i = 0; i < AREA; i++){
        int min_nx = min_x + area_x[i];
        int min_ny = min_y + area_y[i];
        p = dnc(min_nx, min_ny, arr_size/2);
        
        v_zero.push_back(p.first);
        v_one.push_back(p.second);
    }
    
    bool ismerged_zero = true;
    for(int elem : v_zero){
        if(elem != 1){
            ismerged_zero = false;
        }
        ans_p.first += elem;
    }
   
    bool ismerged_one = true;
    for(int elem : v_one){
        if(elem != 1){
            ismerged_one = false;
        }
        ans_p.second += elem;
    }
    if(ismerged_zero && ans_p.second == 0) ans_p.first = 1;
    if(ismerged_one && ans_p.first == 0) ans_p.second = 1;
 
    return ans_p;
}

vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer;
    int arr_size = arr.size();
    arr_global.resize(arr_size, vector<int>(arr_size));
    swap(arr_global, arr);
    
    // for(int i = 0; i < arr_size; i++){
    //     for(int j = 0; j < arr_size; j++){
    //         cout << arr_global[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }

    int min_x = 0, min_y = 0;    
    pair<int, int> ans = dnc(min_x, min_y, arr_size);
    
    answer = {ans.first, ans.second};
    

    
    
    return answer;
}

 

더 좋은 코드?

압축 시도 후 결과를 구하는 방법을 0과1로 따로 구하는 것이 아닌 한 번에 구할 수도 있어보인다. 이 부분은 필자가 봐도 맘에 들지 않는 부분이기 때문에 요령껏(?) 바꿔서 더 좋은 알고리즘을 구하면 될 듯 하다.