[0611] 알고리즘

2630. 색종이 만들기

  비교적 간단했던 분할 정복 문제. 나눠진 정사각형 내 모든 요소가 같지 않으면 (첫 번째 요소와 다른 요소가 한 가지라도 있다면) 다시 그 사각형을 4분할 하는 과정을 거친다.

#include <iostream>
#include <algorithm>
#include <vector>

int white = 0, blue = 0;
int paper[129][129];

void Divide(int col, int row, int side);

int main()
{
  std::cin.tie(NULL);
  std::ios_base::sync_with_stdio(false);

  int n; //한 변의 길이
  std::cin >> n;

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      std::cin >> paper[i][j];
    }
  }

  Divide(0, 0, n);

  std::cout << white << '\n' << blue << '\n';

  return 0;
}

void Divide(int col, int row, int side)
{
  bool isDone = false;

  for (int i = col; i <= col + side - 1; i++)
  {
    for (int j = row; j <= row + side - 1; j++)
    {
      if (paper[col][row] != paper[i][j])
      {
        Divide(col, row, side / 2);
        Divide(col + side / 2, row, side / 2);
        Divide(col, row + side / 2, side / 2);
        Divide(col + side / 2, row + side / 2, side / 2);
        isDone = true;
        break;
      }
    }

    if (isDone) break;
  }

  if (!isDone && paper[col][row] == 1)   
    blue++;

  else if (!isDone && paper[col][row] == 0)
    white++;
}