boj2630-풀이

boj.kr/2630 색종이 만들기 (문제)

풀이

---

분할정복, 재귀

시작점$(Start_x, Start_y)$과, 그 종이의 크기$size$가 주어졌을 때, 해당 종이가 같은 색으로 이루어져 있는지 판단해서 색종이의 수를 구하도록 했다.

(전체 탐색)
check : 시작점으로부터 size * size 크기의 종이가 같은 색으로 채워져 있는지 확인
(재귀를 통한 분할+정복)
rec : 시작점으로부터 size * size 크기의 종이가 몇개의 흰 색/파란 색 정사각형 색종이로 나눌 수 있는지 수를 셈

rec에 대한 설명

1. 시작점으로부터 size * size 크기의 종이가 같은 색으로 이루어져 있다면, 해당 색의 수를 1, 다른 색을 0으로 묶어서 반환합니다.
2. 4분할하여 각 평면의 왼쪽 위 좌표를 기준으로 size / 2 만큼 탐색하여 그 결과를 모두 합하여 반환

주의 : pair<int, int>에서 (y, x)순서로, 그리고 배열에 대해서도 arr[y][x]로 접근했습니다.

구현

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
using namespace std;

bool check(pair<int, int> start, int size, vector<vector<int>> &board) {
  if (size == 1) return true; // <- 없어도 board[start.first][start.second]만 검사해서 true
  int color = board[start.first][start.second];
  for (int y = start.first; y < start.first + size; y++) {
    for (int x = start.second; x < start.second + size; x++) {
      if(board[y][x] != color) return false;
    }
  }
  return true;
}

// overload operator +=, pair<int, int>
pair<int, int> operator+=(pair<int, int> &a, pair<int, int> b) {
  a.first += b.first;
  a.second += b.second;
  return a;
}

pair<int, int> rec(pair<int, int> start, int size, vector<vector<int>> &board) {
  if (check(start, size, board))
    return board[start.first][start.second] == 0 ? make_pair(1, 0) : make_pair(0, 1);
  pair<int, int> mid = {start.first + size / 2, start.second + size / 2};
  pair<int, int> result = {0, 0};
  int next_size = size / 2;
  result += rec(start, next_size, board);
  result += rec({start.first, mid.second}, next_size, board);
  result += rec({mid.first, start.second}, next_size, board);
  result += rec(mid, next_size, board);
  return result;
}

int main()
{
  int n;
  cin >> n;
  vector<vector<int>> board(n, vector<int>(n, false));
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      cin >> board[i][j];
  pair<int,int> res = rec({0, 0}, n, board);
  cout << res.first << '\n' << res.second;
  return 0;
}