색종이 만들기

아래 <그림 1>과 같이 여러 개의 정사각형 칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형 칸들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또한 파란색 색종이를 만들려고 한다.

     <그림 1> 8×8 종이

전체 종이의 크기가 N × N (N = 2^k, k 는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 Ⅰ, Ⅱ, Ⅲ, Ⅳ와 같이 똑같은 크기의 네 개의 (N/2)*(N/2) 색종이로 나눈다. 나누어진 종이 Ⅰ, Ⅱ, Ⅲ, Ⅳ 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

                 <그림 2>

  <그림 3> 처음 나눈 후의 상태

 <그림 4> 두 번째 나눈 후의 상태

<그림 5> 최종적으로 나누어진 색종이들

입력으로 주어진 종이의 한 변의 길이 과 각 정사각형칸의 색 (하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

실행 파일의 이름은 COLOR.EXE로 하고, 프로그램의 실행시간은 5초를 초과할 수 없다. 부분 점수는 없다.

입력

입력 파일명은 INPUT.TXT로 한다. 입력 파일의 첫째 줄에는 전체 종이의 한 변의 길이 이 주어져 있다. 은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 입력 파일의 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

출력 파일명은 OUTPUT.TXT로 한다. 첫째 줄에는 잘라진 하얀색 색종이의 개수를 출력하고 둘째 줄에는 파란색 색종이의 개수를 출력한다.

입력 예제

8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1 
0 1 0 0 1 1 1 1 
0 0 1 1 1 1 1 1 
0 0 1 1 1 1 1 1

출력 예제

9
7

import java.awt.Point;

import java.io.*;

import java.util.Scanner;

 

 

public class ColoredPaper {

    int paper[][];

    int counter=0;

    public BufferedReader in;

    String inputPath="c:/ColoredPaper-input.txt";

    

    public ColoredPaper() throws FileNotFoundException

    {

        Scanner input = new Scanner(new File(inputPath));

        int size=input.nextInt();

        paper=new int[size][size];

        for(int i=0;i<size;i++)

        {

            for(int j=0;j<size;j++)

            {

                paper[i][j]=input.nextInt();

            }

        }

        int count[]=getCount(new Point(0,0),size);

        System.out.println(count[0]+", "+count[1]);

        System.out.println(counter);

    }

    public int[] getCount(Point p,int size)

    {        

        counter++;

        int count[]=new int [2];

        //int [2] 배열 [0]=백, [1]=청

        //0 or 1 count가 0이면 있는건 1바꾸기

        if(size==1)

        {

            count[paper[p.x][p.y]]=1;

            return count;

        }else{

            for(int i=0;i<2;i++)

            {

                for(int j=0;j<2;j++)

                {

                    int temp_count[]=getCount(newPoint(p.x+i*size/2,p.y+j*size/2),size/2);

                    if(temp_count[0]==4&&temp_count[1]==0)

                    {

                        count[0]++;

                    }else if(temp_count[0]==0&&temp_count[1]==4){

                        count[1]++;

                    }else{

                        count[0]+=temp_count[0];

                        count[1]+=temp_count[1];

                    }

                }

            }

            return count;

        }

    }

      

 

    public static void main(String [] args)

    {

        try {

            new ColoredPaper();

        } catch (FileNotFoundException e) {

            // TODO Auto-generated catch block

            e.printStackTrace();

        }

    }

}