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

#include <string>
#include <vector>

using namespace std;

vector<int> answer;

void DFS(int x, int y, int size, vector<vector<int>> &arr);

vector<int> solution(vector<vector<int>> arr) {
    answer.push_back(0);
    answer.push_back(0);
    
    DFS(0, 0, arr.size(), arr);
    
    return answer;
}

void DFS(int x, int y, int size, vector<vector<int>> &arr)
{
    bool noCount = false;
    int val = arr[x][y];
    
    for(int i = x; i < x + size; i++)
    {
        for(int j = y; j < y + size; j++)
        {
            if(arr[i][j] != val) noCount = true;
        }
        
        if(noCount == true) break;
    }
    
    if(noCount == false)
    {
        answer[val]++;
    }
    else
    {
        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);
    }
}

 

풀이

1. 재귀함수를 이용하여 그곳이 모두 0이나 1이면 그 해당 수를 1증가시킨다.
2. 아니라면 4분할로 검색하여 해당지역이 0인지 1인지 확인한다.

 

매우 중요한 점

- 함수에 arr을 전달할 때 값을 전달하면 그 arr를 모두 복사하느라 시간이 엄청 걸린다.
  그러므로 arr를 참조에 의한 호출로 받아와야 시간을 절약할 수 있다.

 

 

참고 자료 : chanheess.tistory.com/98

call by value와 call by reference의 차이