[백준] 1992번 JAVA 쿼드트리 실버 1

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

 

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

// The main method must be in a class named "Main".
class Main {
    public static int N;
    public static int[][] arr;
   	public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];

        for (int i = 0; i <N;i++) {
            String[] str = br.readLine().split("");
            for (int j =0;j <N;j++) {
                arr[i][j] = Integer.parseInt(str[j]);
            }
        }


        recur(0,0,N);
        
        
        
        System.out.println(sb);
    }
    public static void recur(int x, int y, int size) {
        //압축이 가능한지 - 가능하다면 출력값에 추가
        if (isPossible(x,y,size)) {
            sb.append(arr[x][y]);
            return;
        }

        //압축이 가능하지 않으면 기존 size의 절반에서 시작해서 재귀를 돌아야 한다
        int newSize = size / 2;
        sb.append("(");
        recur(x,y,newSize); // 왼쪽 위ㅇ
        recur(x,y+newSize,newSize); //오른쪽 위ㅇ
        recur(x+newSize,y,newSize); //왼쪽 아래ㅇ
        recur(x+newSize,y+newSize,newSize); //오른쪽 아래ㅇ

        sb.append(")"); 
    }
    public static boolean isPossible(int x, int y, int size) {
        int val = arr[x][y];

        for (int i = x; i < x +size;i++) {
            for (int j = y ; j < y + size; j++) {
                if (val != arr[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}

 

분할 정복

문제를 작게 분할한 후 각각을 정복하는 알고리즘. 

분할정복 알고리즘은 문제를 작게 나누어 해결하고 이 해결을 결합하여 원래의 문제를 해결한다