[백준] 2630번 : 색종이만들기 - 자바(JAVA)

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

2630번: 색종이 만들기

 

문제 해석

처음에는 전체크기에서 색종이를 체크하고 그 이후에는 4분할로 나누면서 색종이의 수를 체크합니다.

 

색종이로 체크하기 위해서는 해당하는 모든 구간이 1또는 0이여야 합니다.

 

그림을 기준으로 설명하자면

 

맨 처음에는 8x8 색종이가 구성되는지 확인합니다.

 

이후에 4분면을 제외한 1,2,3분면은 색종이가 완성되지 않았습니다.

 

1,2,3분면은 각각 4x4의 색종이로 나뉘어집니다.

 

1,2,3 분면에서 색종이가 구성되는지 확인합니다.

 

이후에는 다시 1,2,3분면을 각각 2x2의 색종이로 나뉩니다.

 

이렇게하면서 색종이의 수를 구해나갑니다.

 

 

문제 풀이 전 설계

재귀적으로 1,2,3,4분면을 호출하는 구조

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_2630_색종이만들기 {

    static int[][] board;
    static int[] result  = new int[2];

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

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

        board = new int[N][N];

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

        divide(0,0,N,N);

        System.out.println(result[0]);
        System.out.println(result[1]);

    }

    private static void divide(int startY, int startX, int endY, int endX) {

        int start = board[startY][startX];

        if(startY + 1 == endY && startX + 1 == endX){
            result[start]++;
            return;
        }

        int count = 0;

        outer : for(int i=startY; i<endY; i++){
            for(int j=startX; j<endX; j++){
                if(board[i][j] != start){
                    break outer;
                }
                count++;
            }
        }

        if(count == (endY-startY) * (endX - startX)){
            result[start]++;
            return;
        }

        //1사분면
        divide(startY,startX,(startY+endY)/2, (startX+endX)/2);
        //2사분면
        divide(startY,(startX+endX)/2,(endY+startY)/2,endX);
        //3사분면
        divide((startY+endY)/2,startX,endY,(endX+startX)/2);
        //4사분면
        divide((startY+endY)/2,(endX+startX)/2,endY,endX);
    }
}