[코테] 프로그래머스 - 쿼드압축 후 개수 세기 문제 풀이

1. 문제 

• 0과 1로 구성된 2차원 2^n X 2^n 형태의 정사각형 배열 arr 제공
• arr을 사등분하여 4개의 영역으로 분리
• 나뉜 영역 내의 숫자가 모두 0이거나 1이라면 여러개의 숫자를 해당하는 수 하나로 압축
• 모두 압축한 후 arr내의 0과 1의 개수 리턴

2. 풀이

1. 주어진 배열을 모두 탐색해야할 필요성이 있음 ㅡ> 완전탐색(Brute Force) 고려
2. 사등분된 각 영역을 검사
3. 영역이 압축되지 않으면 다시 사등분하여 검사 ㅡ> 분할정복 (Divide and Conquer)
4. 계속해서 사등분하면서 배열 내 모든 부분이 압축 가능한지 검사 (DFS)
5. 결국 배열의 최소 단위인 원소 하나를 검사하게 되는 순간까지 사등분하여 검사
6. 또는, 압축이 되었다면 해당 영역은 끝 (백트래킹)

3. 코드 

#include <bits/stdc++.h>
using namespace std;
vector<int> answer(2,0);
bool IsUniform(vector<vector<int>>& arr, int x, int y, int size)
{
    int pivot=arr[x][y];
    for(int i=x;i<x+size;i++)
    {
        for(int j=y;j<y+size;j++)
        {
            if(arr[i][j]!=pivot) return false;
        }
    }
    return true;
}

void Compress(vector<vector<int>>& arr, int x, int y, int size)
{
    if(IsUniform(arr,x,y,size)) 
    {
        answer[arr[x][y]]++;
        return;
    }
    int half=size/2;
    Compress(arr,x,y,half);
    Compress(arr,x,y+half,half);
    Compress(arr,x+half,y,half);
    Compress(arr,x+half,y+half,half);
}
vector<int> solution(vector<vector<int>> arr) {
    int cursize=arr.size();
    Compress(arr,0,0,arr.size());
    
    return answer;
}

• Compress 함수를 재귀적으로 호출하는 형태로 DFS 구현
• 영역 내의 원소들을 확인하는 함수로 IsUniform 사용
• 모두 확인 후 압축 가능하다면 return하여 불필요한 탐색 방지 (백트래킹)
• 그렇지 않다면 다시 Compress함수 호출하여 영역 사등분 후 검사 (분할 정복)

---

문제 링크

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

프로그래머스