[BOJ] 2630. 색종이 만들기 (C++)

문제

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다.

이때도 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 나눈다.

이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 파란색으로 칠해져 있거나 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

생각할 것

같은 동작을 반복하므로 재귀함수를 사용하고 같은 크기 4개로 나누는 동작을 분할 정복을 활용해보자

코드

#include <iostream>
#include <vector>

using namespace std;

int blue = 0;
int white = 0;

bool confirm(vector<vector<int>> &board, int sx, int sy, int size) { // 모두 같은 색인지 확인
    int start = board[sx][sy];
    for (int i = sx; i < sx + size; i++) {
        for (int j = sy; j < sy + size; j++) {
            if (start != board[i][j]) return false;
        }
    }

    // 모두 같은색이고 파란색이면 blue + 1, 하얀색이면 white + 1
    if (start) blue++; else white++;
    return true;
}

void divide(vector<vector<int>> &board, int sx, int sy, int size) {
    if (confirm(board, sx, sy, size)) return;
    divide(board, sx, sy, size / 2);
    divide(board, sx, sy + (size / 2), size / 2);
    divide(board, sx + (size / 2), sy, size / 2);
    divide(board, sx + (size / 2), sy + (size / 2), size / 2);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N;
    cin >> N;

    vector<vector<int>> board(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }

    divide(board, 0, 0, N);

    cout << white << "\\n";
    cout << blue << "\\n";

    return 0;
}