분할정복

 

 

Divide & Conquer

• 문제를 더 이상 나눌 수 없을 때까지 나누고, 이렇게 나누어진 문제들을 각각 풂으로써 결국 전체 문제의 답을 얻는 알고리즘
• 분할정복 알고리즘의 핵심은 "문제를 잘게 쪼개기", 하지만 문제를 쪼개는 방법에 대해서 정해진 규칙은 없다
• 분할정복의 3가지 구성요소
  1. divide : 문제를 더 작은 문제로 분할
  2. base case : 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제
  3. merge : 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합
• 분할시 생기는 각 하위 문제는 완전히 독립접이므로 네트워크상의 여러 컴퓨터에 의해 병렬처리가 가능
• 예제 BOJ 1780 - 종이의 갯수 https://www.acmicpc.net/problem/1780

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

// 종이 갯수
int Zero =0;
int One = 0;
int MinOne =0;

// (r2-r1+1) x (c2-c1+1) 행렬
short check(vector< vector<short> >& arr, int r1, int r2, int c1, int c2){ 
  //종이가 모두 같은 수로 있는지 검사
  // 모두 같은 수 이면 해당 수 카운트, 하나라도 다르면 -2

  int size = r2-r1+1;
  short res = arr[r1][c1];

  for(int i=r1; i<=r2; i++){
    if( res == -2){
      break;
    }
    for(int j=c1; j<=c2; j++){
      if( res != arr[i][j]){
        res = -2;
        break;
      }
    }
  }

  if( res == -1)
      MinOne++;
  else if (res == 1)
      One++;
  else if( res == 0)
      Zero++;
  return res;
};

// 
void cut( vector< vector<short> >& arr, int r1, int r2, int c1, int c2){
  int size = r2-r1+1;
  
  // base case - 사이즈 확인
  if( size <3){  // 1x1 행렬 
    check(arr, r1, r2, c1, c2); // 해당 숫자 카운트
    return;
  }
  else{ // 3이상, 자를 수 있을정도로 크기 큼
  // 모두 같은 수 인지 check
    short arrSize = (size/3);
    short chk;
    // 11
      chk = check(arr, r1, (r1+arrSize-1), c1, (c1+arrSize-1));
      if(chk == -2)
        cut(arr, r1, (r1+arrSize-1), c1, (c1+arrSize-1));

    // 12
    chk = check(arr, (r1+arrSize), (r1+arrSize+arrSize-1), c1, (c1+arrSize-1));
    if(chk == -2)
      cut(arr, (r1+arrSize), (r1+arrSize+arrSize-1), c1, (c1+arrSize-1));

    //13 *
    chk = check( arr, (r1+arrSize+arrSize), r2, c1, (c1+arrSize-1));
    if(chk == -2)
     cut( arr, (r1+arrSize+arrSize), r2, c1, (c1+arrSize-1));

    // 21
    chk = check(arr, r1, (r1+arrSize-1), (c1+arrSize), (c1+arrSize+arrSize-1));
    if(chk == -2)
      cut(arr, r1, (r1+arrSize-1), (c1+arrSize), (c1+arrSize+arrSize-1));

    // 22
    chk = check(arr, (r1+arrSize), (r1+arrSize+arrSize-1), (c1+arrSize), (c1+arrSize+arrSize-1));
    if(chk == -2)
      cut(arr, (r1+arrSize), (r1+arrSize+arrSize-1), (c1+arrSize), (c1+arrSize+arrSize-1));

    // 23 *
    chk = check(arr, (r1+arrSize+arrSize), r2, (c1+arrSize), (c1+arrSize+arrSize-1) );
    if(chk == -2)
       cut(arr, (r1+arrSize+arrSize), r2, (c1+arrSize), (c1+arrSize+arrSize-1));

    // 31
    chk = check(arr, r1, (r1+arrSize-1), (c1+arrSize+arrSize), c2);
    if(chk == -2)
      cut(arr, r1, (r1+arrSize-1), (c1+arrSize+arrSize), c2);

    // 32
    chk = check(arr, (r1+arrSize), (r1+arrSize+arrSize-1),(c1+arrSize+arrSize), c2);
    if(chk == -2)
      cut(arr, (r1+arrSize), (r1+arrSize+arrSize-1),(c1+arrSize+arrSize), c2);

    // 33
    chk = check(arr, (r1+arrSize+arrSize), r2,(c1+arrSize+arrSize), c2);
    if(chk == -2)
      cut(arr, (r1+arrSize+arrSize), r2,(c1+arrSize+arrSize), c2);

  }

};

int main(){

  //배열 만들기
int N =0;
cin >> N;
vector<vector<short> > arr;
arr.resize(N);

for(int i=0; i<N; i++){
  for(int j=0; j<N; j++){
    short num;
    cin >> num;
    arr[i].push_back(num);
  }
}

short chk = check(arr, 0, (N-1), 0, (N-1));
if( chk == -2)
  cut(arr, 0, (N-1), 0, (N-1));

cout << MinOne <<endl;
cout << Zero << endl;
cout << One << endl;

return 0;
}