[Programmers] 쿼드압축 후 개수 세기(Lv.2)

풀이 소요시간 : 30분

어렵지 않게 구현하여 문제를 풀 수 있었다. 다 풀고 다른 풀이과정도 참고할 겸 찾아봤더니 DFS 를 사용한 재귀 풀이가 정석풀이로 통용되고 있었다. 나는 따로 탐색 알고리즘을 구현하지 않고 순수 구현으로 문제를 풀었는데 말이다.

일단 내 코드를 한번 브리핑 해보면, 딱히 더럽게 나오지는 않았다. 사각형 병합 여부를 반환하는 Check() 함수, 병합을 진행하는 Merge() 함수를 각각 만들어 나름 깔끔하게 구현했다. 하지만 사각형의 변의 길이가 1024 가 아니라 훨씬 더 컸다면 시간초과가 발생했을 수 있다는거다. 따라서 재귀 방식으로 깔끔하게 재풀이하기로 했다.

전체 코드

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

//최종 값
int Fin_0 = 0;
int Fin_1 = 0;

void Dfs(int x, int y, int Size, vector<vector<int>> &arr) {
    
    int Cnt_0 = 0;
    int Cnt_1 = 0;
    
    for(int i = x; i < x + Size; i++)
    {
        for(int j = y; j < y + Size; j++)
        {
            if(arr[i][j] == 0) Cnt_0++;
            else if(arr[i][j]) Cnt_1++;
        }
    }
    
    if(Cnt_0 == 0)
    {
        Fin_1++;
        return;
    }
    else if(Cnt_1 == 0)
    {
        Fin_0++;
        return;
    }
    
    Dfs(x, y, Size / 2, arr);
    Dfs(x + Size / 2, y, Size / 2, arr);
    Dfs(x, y + Size / 2, Size / 2, arr);
    Dfs(x + Size / 2, y + Size / 2, Size / 2, arr);
    
    
}

vector<int> solution(vector<vector<int>> arr) {

    Dfs(0, 0, arr.size(), arr);
    return {Fin_0, Fin_1};
    
}