[C++] 프로그래머스 :: 쿼드압축 후 개수 세기

안녕하세요 뚜디 입니다 :)

코딩테스트 연습 - 쿼드압축 후 개수 세기 | 프로그래머스 (programmers.co.kr)

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

< 프로그래머스 - 쿼드압축 후 개수 세기 (LV2) >

---

1. 연습 문제

2. 문제 풀이

3. 소스 코드

4. 결과

---

1. 연습 문제

※ 문제 설명

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 설명 :

※ 입출력 예 #2 설명 :

 

2. 문제 풀이

입출력 예제 풀이를 보게되면 특정 범위를 탐색했을 때, 우리에게 주어질 수 있는 경우의 수는 3개 존재한다.
Case 1. 특정 범위가 모두 '0' 인 경우 : 더 이상 탐색이 필요하지 않다.
Case 2. 특정 범위가 모두 '1' 인 경우 : 더 이상 탐색이 필요하지 않다.
Case 3. 1,2 모두 아닌 경우 : 더 이상 탐색이 필요하다.
이때, 우리는 3번의 경우를 재귀함수를 통해 1,2번의 Case로 변환 시켜야한다.
또한, 탐색을 진행 하기 전 다음과 같은 2가지 요소가 필요하다.
요소 1. 현재 탐색을 하고자 하는 범위에서, 가장 왼쪽 위 좌표 : 첫 사각형 (0, 0)
요소 2. 현재 탐색을 하고자 하는 정사각형의 한 변의 길이
해당 요소를 적용하여 입출력 예제 문제를 살펴보도록 하겠습니다.

입출력 예제 #1을 살펴보게되면,
1번 사각형 : [(0, 0), 4]
한번 분할한 사각형
1번 사각형 : [(0, 0), 2]
2번 사각형 : [(0, 2), 2]
3번 사각형 : [(2, 0), 2]
4번 사각형 : [(2, 2), 2]
즉, 한 변의 길이를 K라고 표현하게되면
1번 사각형 : [(0, 0), K/2]
2번 사각형 : [(0, 0 + K/2), K/2]
3번 사각형 : [(0 + K/2, 0), K/2]
4번 사각형 : [(0 + K/2, 2), K/2]
로 표현을 할 수 있는것을 알수 있게 된다.

1. flag(Zero, One)을 통해 사각형의 숫자가 압축이 가능한지를 판단한다.
2. "Case 3. 1,2 모두 아닌 경우 : 더 이상 탐색이 필요하다." 의 Case를 따라 재귀 함수를 진행한다.

 

3. 소스 코드

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

using namespace std;

void DFS(int x, int y, int size, vector<int>& answer, vector<vector<int>> &arr) {
    bool Zero = true, One = true;

    for (int i = x; i < x + size; i++) {
        for (int j = y; j < y + size; j++) {
            if (arr[i][j] == 0) One = false;
            if (arr[i][j] == 1) Zero = false;
        }
    }

    if (Zero == true) {
        answer[0]++;
        return;
    }

    if (One == true) {
        answer[1]++;
        return;
    }

    DFS(x, y, size / 2, answer, arr);
    DFS(x, y + size / 2, size / 2, answer, arr);
    DFS(x + size / 2, y, size / 2, answer, arr);
    DFS(x + size / 2, y + size / 2, size / 2, answer, arr);
}

vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer(2, 0);

    DFS(0, 0, arr.size(), answer, arr);

    return answer;
}

 

4. 결과