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

문제

 

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

프로그래머스

 

 

문제풀이

 

재귀를 이용하여 풀었다.

왼쪽 맨 위, 오른쪽 맨 아래 좌표를 구해서 둘의 좌표가 같을 때까지 1/4씩 계속 나눈다.

그다음 왼쪽 맨 위부터 오른쪽 맨 아래까지 모든 칸을 탐색하면서 이전 칸의 값과 같은지를 판별한다.

 

만약 하나라도 다르면 다시 나눈다.

만약 다 같으면 해당 숫자에 해당하는 answer에 값을 1씩 더한다.

 

코드

#include <string>
#include <vector>
using namespace std;
vector<int>answer(2, 0);
vector<vector<int>>board;
int N;

void div(int start_y, int end_y, int start_x, int end_x) {
    if (start_y == end_y) ++answer[board[start_y][start_x]];
    else {
        int prev = board[start_y][start_x];
        for (int y = start_y; y <= end_y; ++y) {
            for (int x = start_x; x <= end_x; ++x) {
                if (prev != board[y][x]) {
                    int mid_y = (start_y + end_y) / 2;
                    int mid_x = (start_x + end_x) / 2;
                    div(start_y, mid_y, start_x, mid_x);
                    div(start_y, mid_y, mid_x + 1, end_x);
                    div(mid_y + 1, end_y, start_x, mid_x);
                    div(mid_y + 1, end_y, mid_x + 1, end_x);
                    return;
                }
                prev = board[y][x];
            }
        }
        ++answer[board[start_y][start_x]];
    }
}

vector<int> solution(vector<vector<int>> board) {
    N = board.size();
    ::board = board;
    div(0, N - 1, 0, N - 1);
    return answer;
}