[알고리즘 문제풀이] 백준 1780 종이의 개수 (JAVA)

목차

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

1780번: 종이의 개수

 

/**
 * 분할정복 문제
 * 
 * 1) 숫자 파악
 * 
 * 2) 맞지 않으면, 9분할
 * 
 * 3) 분할 내에서 확인
 */

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

public class BJ1780_종이의개수 {
    
    public static int[][] arr;
    public static int[] answer = new int[3];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        int n = Integer.parseInt(br.readLine());
        
        arr = new int[n][n];

        StringTokenizer st;

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

        slice(n,0,0);
        for(int i = 0; i < answer.length; i++){
            System.out.println(answer[i]);
        }
    }

    public static void slice(int size, int n, int m){

        // 다 같은 숫자면 더하기
        if(numCheck(size,n,m)){
            if(arr[n][m] == -1){
                answer[0]++;
            }else if(arr[n][m] == 0){
                answer[1]++;
            }else{
                answer[2]++;
            }
        // 아니면 9분할
        }else{
            int newsize = size/3;

            slice(newsize, n, m); // 1사분면
            slice(newsize, n,m+newsize); // 2사분면
            slice(newsize, n,m+newsize*2); // 3사분면
            
            slice(newsize, n+newsize, m); // 4사분면
            slice(newsize, n+newsize,m+newsize); // 5사분면
            slice(newsize, n+newsize,m+newsize*2); // 6사분면
            
            slice(newsize, n+newsize*2, m); // 7사분면
            slice(newsize, n+newsize*2,m+newsize); // 8사분면
            slice(newsize, n+newsize*2,m+newsize*2); // 9사분면
        }
    }

    public static boolean numCheck(int size, int n, int m){
        int first = arr[n][m];
        boolean check = true;
        for(int i = n; i < n+size; i++){
            for(int j = m; j < m+size; j++){
                if(first != arr[i][j]){
                    check = false;
                    break;
                }
            }
        }
        return check;
    }
}