[백준] 2630번

divide conquer을 잘 사용하면 풀리는 문제다

#include <iostream>
#include <vector>

std::vector<std::vector<int>> map;
int white = 0;
int blue = 0;

bool is_same_color(int x, int y, int size) {
    int color = map[x][y];
    for (int i = x; i < x+size; i++) {
        for (int j = y; j < y+size; j++) {
            if (color != map[i][j]) {
                return false;
            }
        }
    }
    return true;
}

void divide(int x, int y, int size) {
    if (is_same_color(x, y, size)) {
        if (!map[x][y]) {
            white++;
        } else {
            blue++;
        }
        return;
    }
    int half = size / 2;
    divide(x, y, half);
    divide(x, y + half , half);
    divide(x + half, y, half);
    divide(x + half, y+half, half);
}


int main() {
    int n;
    std::cin >> n;
    map.resize(n, std::vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            std::cin >> map[i][j];
        }
    }
    divide(0, 0, n);
    std::cout << white << "\n" << blue << std::endl;
    return 0;
}