[JAVA] 백준 1790 종이의 개수

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

1780번: 종이의 개수

 

- N*N 크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1,0,1 중 하나가 저장되어 있다.

- 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자를려고 한다.

 

1) 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.

2) 1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 1)의 과정을 반복한다. 

 

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

 

 

문제 풀이 

 

- 앞서 쿼드 트리, 색종이 만들기와 비슷하게 풀이 

- 9개의 영역으로 나누어야 하기 때문에 각 나눠진 파티션은 원래 크기의 1/3씩 감소 

 

 

정답 

 

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

public class Main {
    static int board[][];
    static int cnt1 = 0; //-1 개수
    static int cnt2 = 0; //0 개수
    static int cnt3 = 0; // 1 개수 
    
    public static void main(String[] args)throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        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());
            }
        }
        
        partition(0,0,n);
        
        bw.write(cnt1+"");
        bw.newLine();
        
        bw.write(cnt2+"");
        bw.newLine();
        
        bw.write(cnt3+"");
        bw.newLine();
        
        bw.flush();
        bw.close();
        
    }
    
    public static void partition(int row, int col, int size)
    {
        if(check(row,col,size))
        {
            if(board[row][col]==-1)
            {
                cnt1++;
            }
            else if(board[row][col]==0)
            {
                cnt2++;
            }
            else
            {
                cnt3++;
            }
            return;
        }
        
        //숫자가 다를 경우 
        int newSize = size/3;
        
        //재귀 호출
        partition(row,col,newSize);
        partition(row,col+newSize, newSize);
        partition(row,col+2*newSize, newSize);
        
        partition(row+newSize,col,newSize);
        partition(row+newSize,col+newSize,newSize);
        partition(row+newSize,col+2*newSize,newSize);
        
        partition(row+2*newSize, col, newSize);
        partition(row+2*newSize, col+newSize, newSize);
        partition(row+2*newSize, col+2*newSize, newSize);
        
    }
    
    //현재 나뉜 숫자가 같은지 체크 
    static boolean check(int row, int col, int size)
    {
        int num = board[row][col]; 
        
        for(int i=row; i<row+size; i++)
        {
            for(int j=col; j<col+size; j++)
            {
                if(num != board[i][j])
                {
                    return false;
                }
            }
        }
        return true;
    }
}