[BOJ] 백준 1992 쿼드트리

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


이 문제는 Divide and Conquer 문제로, 절반씩 케이스를 줄여나간 후 최소단위에 도달하게 되면 합쳐서 정답에 도달하는 문제 입니다.

쿼드트리는 가로세로 2^n 으로 절반으로 나누기 좋게 되어있습니다.

만약에 입력받은 범위내 원소들이 모두 0 또는 1 (즉, 같은 색깔) 이 아니라면
그 범위를 정확히 4등분 하여 다시 같은색깔인지 확인합니다.

만약, 같은색깔이라면 그 값을 출력해주면 되는 문제 입니다.

소스코드 :

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

bool IsSameColor(int x1, int x2, int y1, int y2 , vector<vector<int> > & v) {

 int origin = v[x1][y1]; 
 for (int i = y1; i < y2; i++) {
  for (int j = x1; j < x2; j++) {
  
   if (origin != v[j][i])
    return false;
  }
 }
 return true;
}
void QuadTree(int x1, int x2, int y1, int y2, vector<vector<int> > & v) {
 if (x2 == 0 || y2 == 0)
  return;
 if ( ! IsSameColor(x1, x2, y1, y2, v)) {
  cout << "(";
  QuadTree(x1, ((x1+x2) / 2), y1, ((y1+y2) / 2), v);
  QuadTree(((x1 + x2) / 2), x2, y1, ((y1 + y2) / 2), v);
  QuadTree(x1, ((x1 + x2) / 2), ((y1 + y2) / 2), y2, v);
  QuadTree(((x1+x2) / 2), x2, ((y1+y2) / 2), y2, v);
  cout << ")";
 }
 else {
  cout <<  v[x1][y1];  
 }
}

int main() {

 int n;
 cin >> n;
 cin.ignore();
 vector<vector<int> > v(n, vector<int>(n));
 string str;
 for (int i = 0; i < n; i++) {
  getline(cin, str, '\n');
  for (int j = 0; j < n; j++) {
   v[j][i] = str[j] - 48; 
  }
 }

       QuadTree(0, n, 0, n, v);

}