[BOJ] 백준 1780 종이의 개수

문제링크 : https://www.acmicpc.net/problem/1780

이 문제 역시 분할정복 유형입니다.
이전 쿼드트리는 4분할 하였지만, 이 종이는 9분할 입니다.

개념 자체는 쿼드트리와 같아, 아이디어는 문제 없었지만
의외로 시간을 많이쓰게 되었는데, 그 이유는 다음과 같습니다.

1. 벡터로 행렬을 구현하였는데 행/열 개념을 헷갈렸다.
2. 9분할 하였을 때, 범위를 어떻게 줘야할 지 헷갈렸다.

1번은 행/열 을 반대로 생각하고 풀어서 어려움을 겪었고
2번은 9분할을 단지 (x1+x3)/3 과 ((x1+x3)*2)/3 으로만 해서 벡터범위 초과가 났습니다.
2번에서, 저렇게 하면 안되고 x1 + offset, x1 + offset*2 이렇게 해야 했습니다.

그 외에는 어려움은 없었습니다.
재귀 탈출문은 SameColor가 있는 조건문이 if-else로 되었고, else문에서 해당 색상을 검색하기 때문에 따로 구현하지 않아도 되었습니다.


소스코드 :

#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;

int num;
int cnt[3] = { 0,0,0 };

bool SameColor(int x1, int x3, int y1, int y3, vector<vector<int> >&v) {
 
 for (int i = y1; i < y3; i++) {
  for (int j = x1; j < x3; j++) {
   if (v[y1][x1] != v[i][j]) {
    return false;
   }
  }
 }

 return true;
}



void Paper(int x1, int x3, int y1, int y3, vector<vector<int> >&v) {

 if (!SameColor(x1, x3, y1, y3, v)) {
 
  
  int offset_x = (x3 - x1) / 3;
  int offset_y = (y3 - y1) / 3;


  //1
  Paper(x1, x1 + offset_x, y1, y1 + offset_y, v);
  //2
  Paper(x1 + offset_x, x1 + offset_x * 2, y1, y1 + offset_y, v);
  //3
  Paper(x1 + offset_x * 2, x3, y1, y1 + offset_y, v);

  //4
  Paper(x1, x1 + offset_x, y1 + offset_y, y1 + offset_y * 2, v);
  //5
  Paper(x1 + offset_x, x1 + offset_x * 2, y1 + offset_y, y1 + offset_y * 2, v);
  //6
  Paper(x1 + offset_x * 2, x3, y1 + offset_y, y1 + offset_y * 2, v);

  //7
  Paper(x1, x1 + offset_x, y1 + offset_y * 2, y3, v);
  //8
  Paper(x1 + offset_x, x1 + offset_x * 2, y1 + offset_y * 2, y3, v);
  //9
  Paper(x1 + offset_x * 2, x3, y1 + offset_y * 2, y3, v);

 }
 else {
  if (v[y1][x1] == -1) cnt[0] = cnt[0] + 1;
  else if (v[y1][x1] == 0) cnt[1] = cnt[1] + 1;
  else cnt[2] = cnt[2] + 1;
 }
 
 
 

}


int main() {
 cin.tie(NULL);
 ios_base:: sync_with_stdio(false);
 cin >> num;
 vector<vector<int> > v(num, vector<int>(num));

 for (int i = 0; i < num; i++) {
  for (int j = 0; j < num; j++) {
   cin >> v[i][j];
  }
 }


 Paper(0, num, 0, num, v);
 for (int i = 0; i < 3; i++) {
  cout << cnt[i] << endl;
 }
}