[Java] 백준 1780번 : 종이의 개수

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

1780번: 종이의 개수

[문제]

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

 

[입력]

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

[출력]

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

[예제 입력]

[풀이과정]

앞서 푼 문제중에 [1992번 : 쿼드트리 https://geumba.tistory.com/26?category=1020363] , [ 2630 : 색종이 만들기 https://geumba.tistory.com/23?category=1020363] 문제와 흡사하다. 저 문제들과 다른점이 있다면 4분할이 아닌 9분할을 해줘야 한다는 점이다. 그 이외에 풀이는 거의 똑같다! 

[코드]

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

public class Main {

        static int [][]square ;
        static int []answer ;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;

        int N = Integer.parseInt(br.readLine()); //종이의 크기
        answer = new int[3]; // 0 은 -1의 개수 / 1은 0의 개수/ 2는 1의 개수

        square = new int[N][N];

        for(int i = 0 ; i < N ; i++){ //2차원 배열에 입력값 넣기
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0 ; j < N; j++){
                square[i][j]=Integer.parseInt(st.nextToken());
            }
        }

        division(0,0,N);
        System.out.println(answer[0]); // -1
        System.out.println(answer[1]); // 0 
        System.out.println(answer[2]); // 1

    }


    public static void division(int x , int y , int N){

        if (check(x,y,N)){ //영역이 다 같은 수 인지 체크한다.
            answer[square[x][y]+1]++;
            return;
        }


        int size = N/3;

        division(x,y,size); //1
        division(x,y+size,size);//2
        division(x,y+size*2,size);//3

        division(x+size,y,size);//4
        division(x+size,y+size,size);//5
        division(x+size,y+size*2,size);//6


        division(x+size*2,y,size);  // 7
        division(x+size*2,y+size,size); //8
        division(x+size*2,y+size*2,size); //9




    }
    public static boolean check (int x, int y ,int N){

        int firstBlock = square[x][y];

        for(int i = x; i <x+N; i++){
            for (int j = y; j <y+N ; j++){
                if(firstBlock!=square[i][j]){
                    return false;
                }
            }
        }

        return true;

    }

}

 

[결과]