[백준 1780]-[분할정복]-종이의 개수 (JAVA)

문제 링크 : https://www.acmicpc.net/problem/1780

---

이 문제는 분할정복으로 풀어야 한다. 

입력받은 사이즈가 9 라면 총 9*9 개의 모든 좌표가 같아야 하나의 정사각형 종이가 완성된다. 

그럼 9*9개의 수가 같지 않다면? 9등분을 한뒤에 다시 정사각형 종이가 나오는지 확인해야 된다.

사이즈 9를 3으로 나눠 다시 확인하고 여기서도 정사각형 종이가 나오지 않는다면 3으로 다시 나눠서 확인해야한다. 

이문제의 조건은 사이즈는 무조건 3의 배수로 입력 된다고 한다.

첫째 줄에 N(1≤N≤3^7, N은 3^k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

3으로 나눠지지 않을 걱정은 안해도 되고 그럼 이 문제를 어떻게 푸는지 간단하게 정리하면

1) 사이즈만큼 하나의 종이로 만들어 지는지 확인

2) 하나의 종이로 만들어진다면 해당 좌표에 해당되는 값의 count를 1 증가 시켜준다. 

3) 하나의 종이로 만들어 지지 않는다면 길이를 3으로 나누고 총 9등분된 좌표의 시작점에서 다시 조회를 한다. 

순서 3번에 대해서는 이해가 되지 않을 수 있는데 9등분한 종이를 각각의 종이라 생각하고 그것들에대해서 따로따로 조회를 해야 한다. 

그리고 입력받는 수가 -1, 0, 1 이렇게 세 수가 입력이 되는데 각 수의 count는 정수형 배열에 좌표로 저장하고 싶어서 나는 -1, 0, 1을 1씩 더해서 0, 1, 2로 만든뒤 계산했다. -1은 인덱스에 들어갈 수 없기 때문에 0, 1, 2 로 만든뒤 계산하면 번거롭지 않게 계산할 수 있다. 

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static int size;
    
    public static int[] cnt;
    public static int[][] arr;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        size = Integer.parseInt(br.readLine());
        
        cnt = new int[3];
        arr = new int[size][size];
        
        StringTokenizer st = null;
        for(int i=0; i < size; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j < size; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken()) + 1;
            }
        }
        
        divideAndConquer(0,0,size);
        
        System.out.println(cnt[0] + "\n" + cnt[1] + "\n" + cnt[2]);
        
    }
    
    public static boolean isAble(int r, int c, int len) {
        int t = arr[r][c];
        
        for(int i = r; i < r+len; i++) {
            for(int j = c; j < c+len; j++) {
                if(t != arr[i][j]) return false;
            }
        }
        return true;
    }
    
    public static void divideAndConquer(int r, int c, int len) {
        // 같으면 해당 수의 count를 1 증가 시켜준다.
        if(isAble(r, c, len)) {
            cnt[arr[r][c]] += 1;
        }else {
            // 다르면 len을 3으로 나눠서 3으로 나눈거에 대한 첫 인덱스에 해당 되는 좌표로 재호출한다.
            // 0 ~ 8 의 len이 9였는데 만족이 안됐다면 len이 3이 되고 각 시작점 {0,0}, {0,3}, {0,6} 으로 다시 재호출한다.
            //                                                        {3,0}, {3,3}, {3,6}
            //                                                        {6,0}, {6,3}, {6,6}
            // 현재 좌표 + 새로운길이 * 0 or 1 or 2 -> 9로 나눈 새로운 좌표가 나온다.
            
            int newLen = len/3;
            
            for(int i=0; i < 3; i++) {
                for(int j=0; j < 3; j++) {
                    divideAndConquer(r+newLen*i, c+newLen*j, newLen);
                }
            }
        }
    }
}