[JAVA]백준 2630번: 색종이만들기

www.acmicpc.net/problem/2630

2630번: 색종이 만들기

 

1. 문제 설명

 

전체 종이가 같은 색으로만 이루어질 때까지 반씩 나누어 하얀색, 파란색 색종이의 개수를 구하는 문제이다.

N은 2,4,6,8,32,64,128중 하나이다.

N이 최대 128이라고 가정하면 최대 연산 횟수는 128^2+64^2*4+32^2*8+16^2*16+8^2*32+4^2*64+1^2*128=48236이다.

( 128*128개의 배열을 1*1의 색종이가 될 때까지 분할하고 확인한다고 가정했을 때)

따라서 재귀 함수로 풀어도 시간제한(1초)에 걸리지 않을 것이라고 판단하고 재귀 함수로 풀었다.

 

현재 N 크기의 색종이가 같은 색을 가지고 있다면 그 색의 색종이 개수를 증가시키고

같은 색을 가지고 있지 않다면 색종이를 x 길이 2/N, y 길이 2/N으로 나누어 총 4개로 나누고

각각 함수를 재귀 호출했다.

 

2. 코드

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static int [][] paper=new int[128][128];
    public static int[] number=new int[2];

    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);


        int num=scan.nextInt();

        for(int x=0;x<num;x++){
            for(int y=0;y<num;y++)
                paper[x][y]=scan.nextInt();
        }

        paper_check(num,0,0);

        System.out.println(number[0]+"\n"+number[1]);

        scan.close();
    }


    public static void paper_check(int num,int x_index,int y_index){

        boolean flag=true;
        int base=paper[x_index][y_index];

        for(int x=x_index;x<x_index+num;x++){
            for(int y=y_index;y<y_index+num;y++){
                if(base!=paper[x][y]){
                    flag=false;
                    break;
                }
            }
            if(!flag)
                break;
        }

        if(flag){
            number[base]++;
        }else{
            int divide=num/2;

            paper_check(divide,x_index,y_index);
            paper_check(divide,x_index+divide,y_index);
            paper_check(divide,x_index,y_index+divide);
            paper_check(divide,x_index+divide,y_index+divide);
        }
    }

}