BOJ. 1992

#BOJ1992

쿼드트리

이 문제를 보면서 정말 클래스3에 엄청나게 많은 분할정복 문제가 있다는 것을 깨달았다. 하지만 정말 결이 비슷해서 지난번에 풀었던 문제의 과정에 괄호만 추가하였다. 풀이가 궁금하다면 전과 마찬가지로 이전 코드를 참고하는 것이 좋아보인다. 굳이 하나를 첨언하자면 띄어쓰기가 없어서 스트링으로 받아서 배열에 접근하는 방향으로 문제를 해결하였다.

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

int N;
string arr[64];

bool check(int r, int c, int N){
   for (int i = r; i < r + N; i++){
       for (int j = c; j < c + N; j++){
           if (arr[r][c] != arr[i][j]) {
               return false;
           }
       }
   }
   return true;
}

void solve(int r, int c, int N){
   if (check(r, c, N)){
       cout << arr[r][c];
   }
   else{
       N = N / 2;
       cout << '(';
       for (int i = 0; i < 2; i ++){
           for (int j = 0; j < 2; j++){
               solve(r + N * i, c + N * j, N);
           }
       }
       cout << ')';
   }
}


int main(){
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);
   
   cin >> N;
   for (int i = 0; i < N; i++){
       cin >> arr[i];
   }
   solve(0, 0, N);
   return 0;
}