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

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

프로그래머스

---

문제풀이

배열을 4개로 분할만 해주면 되는 문제이다.

dfs 함수를 만들었는데 이 함수는, 탐색할 사각형의 행,열의 시작 인덱스, 끝인덱스+1의 값을 갖는다.

맨 처음 dfs가 호출되면 가장 처음 값을 저장한 뒤, 인자로 들어온 인덱스를 순환하며 값이 다른지 확인한다. 값이 다르다면 사각형을 4개로 분할해야 한다. 값이 모두 같다면, 해당 사각형은 하나로 합쳐진다. 그러므로 0 또는 1에 해당하는 정답을 1 증가시켜주면 된다. 그렇게 쭉쭉가다가 만약 사각형이 하나일 경우까지 간다면 그 값을 정답에 더해주면 된다.

백준으로 비슷한 문제를 풀어본 경험이 있어서 빠르게 풀 수 있었다.

 

코드를 보면 이해가 훨씬 빠르게 될것이다.

 

#include <string>
#include <vector>

using namespace std;

vector<int> answer(2);

void dfs(int start_row, int end_row, int start_col, int end_col, vector<vector<int>>& v) {
    int value = v[start_row][start_col];
    // 하나 남았을 경우
    if(start_row+1 == end_row) {
        answer[value]++;
        return;
    }
    for(int i=start_row; i<end_row; i++) {
        for(int j=start_col; j<end_col; j++) {
            if(value != v[i][j]) {
                dfs(start_row, (start_row+end_row)/2, start_col, (start_col+end_col)/2, v);
                dfs((start_row+end_row)/2, end_row, start_col, (start_col+end_col)/2, v);
                dfs(start_row, (start_row+end_row)/2, (start_col+end_col)/2, end_col, v);
                dfs((start_row+end_row)/2, end_row, (start_col+end_col)/2, end_col, v);
                return;
            }
        }
    }
    answer[value]++;
}

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