[분할 정복] BOJ 1992 쿼드 트리

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

 

 

문제 해결 알고리즘

 

nXn 사분면에서 모든 숫자들이 같지 않으면 또 사분면으로 나누어서 분할 정복을 실행해준다. 만약 같다면 그 숫자를 출력해준다.

 

소스 코드

 

#include <bits/stdc++.h>
#define MAX 65
using namespace std;

int N;
int arr[MAX][MAX];

void div_n_coqr(int n, int x, int y){

  bool flag = true;

  for(int i=x;i<n+x;i++){
    for(int j=y;j<n+y;j++){
      if(arr[x][y] != arr[i][j]) flag = false;
    }
  }

  if(!flag){
    cout << '(';
    div_n_coqr(n/2, x, y);
    div_n_coqr(n/2, x, y+n/2);
    div_n_coqr(n/2, x+n/2, y);
    div_n_coqr(n/2, x+n/2, y+n/2);
    cout << ')';
  }
  else cout << arr[x][y];
}

int main(){

  cin >> N;
  string str;

  for(int i=0;i<N;i++) {
    cin >> str;
    for(int j=0;j<N;j++){
      arr[i][j] = str[j] - '0';
    }
  }
    
  div_n_coqr(N, 0, 0);
}