[프로그래머스] 쿼드압축 후 개수 세기 / 쿼드트리, 재귀

 

Level. 2

 

문제

0과 1로 이루어진 2^n x 2^n 크기의 2차원 정수 배열 arr이 있습니다.
당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.
당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.
arr이 매개변수로 주어집니다.
위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

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

 

 

입출력 예

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

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

 

 

풀이

#include <string>
#include <vector>
#include <iostream>
using namespace std;

static vector<int> answer;

void quad( const vector<vector<int>> &arr,int x, int y, int n){
    int num = arr[x][y];
    for(int i=x; i<x+n; i++){
        for(int j=y; j<y+n; j++){
            if(arr[i][j] != num){ // 1칸이라도 다르면 다시 칸을 2로 분할
                quad(arr, x    , y    , n/2);
                quad(arr, x+n/2, y    , n/2);
                quad(arr, x    , y+n/2, n/2);
                quad(arr, x+n/2, y+n/2, n/2);
                return;
            }
        }
    }
    answer[num] += 1;
    return;
}

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

 

 

 

쿼드트리

• 각 내부 노드가 정확히 4개의 자식을 갖는 트리 데이터 구조이며, 구하는 레코드가 나타날 때까지 4개로 등분하여 검색을 행한다. 
• 공간을 4개의 정사각형으로 분할하는 원리로, 넓은 지역에 대한 빠른 검색이 가능하다. 

출처 : http://blog.notdot.net/

 

 

 

해결방법

1. 탐색한 영역이 모두 1인경우. answer[1]에 +1
2. 탐색한 영역이 모두 0인경우. answer[0]에 +1
3. 탐색한 영역 내부 숫자가 하나라도 다른 경우 -> 4 등분하여 재탐색(재귀)

 

** 추가정보 

함수를 quad(arr, x, y, n); 로 호출 할 경우 각각 매개변숫값의 주소로 접근해서 값을 사용하는 것이 아니라 새로운 값을 할당하여 호출하게 된다.
새로 메모리영역에 값을 할당하는 비용이 크기 때문에 함수 안에서 값을 변경하지 않을 경우 매개변수로 받은 값을 사용하는 게 합리적이므로, 매개변수를 참조로 호출하면 새로 메모리를 할당하지 않아 시간적 공간적으로 더 효율적이다.  

-> 변경 전 : void quad( vector <vector <int>> arr, int x, int y, int n){.. } 

-> 변경 후 : void quad( const vector <vector <int>> &arr, int x, int y, int n){.. }

- const : 상수화
- & : 참조자. 객체의 값을 담는 공간
- * : 포인터. 객체의 주소를 가리키는 변수

---

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

프로그래머스

https://en.wikipedia.org/wiki/Quadtree

Quadtree - Wikipedia

http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves

Damn Cool Algorithms: Spatial indexing with Quadtrees and Hilbert Curves - Nick's Blog