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

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 정사각형 안에 있는 숫자가 전부 같지 않으면 사각형을 4개로 나눠서 탐색하면 되는 문제다.

 

먼저 정사각형의 모든 숫자가 같은지 탐색한다.

 

이때 전부 숫자가 같다면 그 숫자가 0일 경우 0의 개수를 1 증가시키고, 1의 개수를 1 증가시키면 된다.

 

만약 다르다면 4개로 쪼개서 다시 탐색하면 된다. (재귀적으로 탐색)

 

4개로 쪼갤 때, x와 y좌표의 시작점과 끝점을 이용해 절반으로 나눠서 사용하면 된다.

ex) [x좌표 시작, x좌표 중간], [x좌표 중간+1, x좌표 끝] 으로 경우를 나눌 수 있다 (y도 마찬가지)

 

​

[아이디어 정리]

1. 정사각형안의 모든 수가 같은지 검사한다.
2. 만약 모든 수가 같다면, 그 수가 0인지 1인지 센 다음 개수를 return한다.
3. 만약 다르다면, 4개로 쪼개고 쪼갠 범위를 다시 탐색해 개수를 return받는다.
4. return 받은 값을 더해서 return한다.

 

 

 

Code

 

 

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

vector<int> Calc(int xSt, int xEd, int ySt, int yEd, vector<vector<int>> &arr)
{
    vector<int> retAns(2,0);
    int num=arr[xSt][ySt];
    bool flag=false;
    for (int i=xSt;i<=xEd; i++)
    {
        for (int j=ySt; j<=yEd; j++)
        {
            if (num!=arr[i][j])
            {
                flag=true;
                i=xEd+1; //종료
                break;
            }
        }
    }
    vector<int> tempV;
    if (flag)
    {
        int xMid=(xSt+xEd)/2, yMid=(ySt+yEd)/2;
        tempV=Calc(xSt,xMid,ySt,yMid,arr);
        retAns[0]+=tempV[0],retAns[1]+=tempV[1];
        tempV=Calc(xMid+1,xEd,ySt,yMid,arr);
        retAns[0]+=tempV[0],retAns[1]+=tempV[1];
        tempV=Calc(xSt,xMid,yMid+1,yEd,arr);
        retAns[0]+=tempV[0],retAns[1]+=tempV[1];
        tempV=Calc(xMid+1,xEd,yMid+1,yEd,arr);
        retAns[0]+=tempV[0],retAns[1]+=tempV[1];
    }
    else
    {
        if (num==1)
            retAns[1]=1;
        else
            retAns[0]=1;
    }
    return retAns;
}

vector<int> solution(vector<vector<int>> arr) {
    return Calc(0, arr.size()-1,0, arr.size()-1, arr);
}

 

---

재귀함수에 대한 이해가 있으면 쉽게 풀 수 있는 문제다

처음에 범위를 arr.size()-1로 시작해야 하는데  arr.size()로 시작해서 오류가 났었다;;

 

프로그래머스