분할 정복

분할정복은

크고 방대한 문제를 나눌 수 있는 문제 단위로 나눠가면서 푸는 문제
즉 큰 단위에서 나눌 수 있다면 그것보다 작은 단위로, 다시 나눌 수 있다면 그것보다 작은 단위로 쪼개가면서 풀어서 합치는 문제이다.

이 알고리즘은 "색종이 접기"처럼 무언가 접어서 분할될 수 있도록 문제에서 그 기준과 단위가 주어진다.

결국 저기서 작은 단위로 쪼개서 다시 한다 = 재귀함수를 이용한다.

라고 생각하면 된다.

백준에 있는 몇 개의 응용문제를 풀면서
개념을 확립해보자.

응용문제 백준의 1780번 문제

를 풀어보자

여기서 보면
기준 : 한장에 표현되는 숫자가 다를경우
단위 : 9장으로 만든다. -> 재귀함수 9번 호출

import java.util.*;
import java.io.*;

public class Main{

    static int zero=0;
    static int one=0;
    static int m_one=0;

    static int[][] arr ;

    static void partition(int row, int col, int size){

      if(check(row,col,size)){
          if(arr[row][col]==0) zero++;
          if(arr[row][col]==1) one++;
          if(arr[row][col]==-1) m_one++;
      }else{

          int SIZE = size/3;

          partition(row,col,SIZE);
          partition(row,col+SIZE,SIZE);
          partition(row,col+2*SIZE,SIZE);

          partition(row+SIZE,col,SIZE);
          partition(row+SIZE,col+SIZE,SIZE);
          partition(row+SIZE,col+2*SIZE,SIZE);

          partition(row+2*SIZE,col,SIZE);
          partition(row+2*SIZE,col+SIZE,SIZE);
          partition(row+2*SIZE,col+2*SIZE,SIZE);


      }

    }

    static boolean check(int row, int col, int size){

        int check_num =arr[row][col];

        for(int i=row;i<row+size;i++){
            for(int j=col;j<col+size;j++){
                if(arr[i][j] != check_num)
                    return false;
            }
        }
        return true;

    }

    public static void main(String[] args)throws IOException{
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int N = Integer.parseInt(br.readLine());

       arr = new int[N][N];

       for(int i=0;i<N;i++){
           StringTokenizer st = new StringTokenizer(br.readLine()," ");
           for(int j=0;j<N;j++){
               arr[i][j]= Integer.parseInt(st.nextToken());
           }
       }


       partition(0,0,N);

       bw.write(Integer.toString(m_one)+"\n");
       bw.write(Integer.toString(zero)+"\n");
       bw.write(Integer.toString(one)+"\n");
       bw.flush();
       bw.close();
       br.close();

    }



}

응용문제 백준의 1992번

을 풀어보고자 한다.

쿼드트리 문제로 위 문제와 똑같은 방식으로 진행되나

• 재귀함수 호출 순서가 정해져있다.
• 압축한 결과를 차례대로 괄호 안에 묶는다는 것!
  보면 저 괄호가 더 작은 단위로 쪼개지는 것을 결정할 때 생긴다

import java.util.*;
import java.io.*;

public class Main{
    static int N;
    static char[][] arr;
    static StringBuilder sb = new StringBuilder();

    static boolean check(int row, int col, int size){

        char one_zero = arr[row][col];

        for(int i=row;i<row+size;i++){
            for(int j=col;j<col+size;j++){
                if(arr[i][j] != one_zero)
                    return false;
            }
        }
        return true;

    }
    static void partition(int row, int col, int size){


        if(check(row,col,size)){
            if(arr[row][col]=='1') sb.append("1");
            if(arr[row][col]=='0') sb.append("0");
        }else{
            int SIZE = size/2;
            sb.append("(");
            partition(row,col,SIZE);//왼쪽 위
            partition(row, col+SIZE, SIZE);//오른쪽 위

            partition(row+SIZE, col,SIZE);//왼쪽 아래
            partition(row+SIZE, col+SIZE, SIZE);//오른쪽 아래
            sb.append(")");
        }


    }



    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        arr = new char[N][N];

        for(int i=0;i<N;i++){
            String input = br.readLine();
            for(int j=0;j<N;j++){
                arr[i][j] = input.charAt(j);
            }
        }


        partition(0,0,N);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();


    }



}