[Algorithm] 백준 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로만 채워진 종이의 개수를 출력한다.

 

[ 예제 입력 ]

9

0 0 0 1 1 1 -1 -1 -1

0 0 0 1 1 1 -1 -1 -1

0 0 0 1 1 1 -1 -1 -1

1 1 1 0 0 0 0 0 0

1 1 1 0 0 0 0 0 0

1 1 1 0 0 0 0 0 0

0 1 -1 0 1 -1 0 1 -1

0 -1 1 0 1 -1 0 1 -1

0 1 -1 1 0 -1 0 1 -1

 

[ 예제 출력 ]

10

12

11

 

---

 

import java.io.*;
import java.util.*;

public class Main {
	
	static int one, zero, minusOne;
	
	private static boolean sameNumber (int[][]paper, int row, int column, int size) {
		int number = paper[row][column];
		
		for (int i = row; i < row+size; i++) {
			for (int j = column; j < column+size; j++)
				if (paper[i][j] != number)	return false;
		}
		return true;
	}
	
    
	public static void paperNum (int[][] paper, int row, int column, int size) {
		if (size == 1 || sameNumber(paper, row, column, size)) {
			if (paper[row][column] == 1)	one++;
			else if (paper[row][column] == 0)	zero++;
			else	minusOne++;
			return;
		}
		
		int newSize = size / 3;
		
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++)
				paperNum(paper, row + newSize * i, column + newSize * j, newSize);
		}
	}
	
    
	public static void main (String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken()); // 전체 종이의 한 변의 길이
		int[][] paper = new int[N][N];
		one = 0; zero = 0; minusOne = 0;
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++)
				paper[i][j] = Integer.parseInt(st.nextToken()); // 1 or 0 or -1
		}
		
		paperNum(paper, 0, 0, N);
		System.out.println(minusOne + "\n" + zero + "\n" + one);
	}
}