백준 1780 종이의 개수 JAVA

종이의 개수

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

난이도 : 실버 2

 

문제 

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

만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
(1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.
이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

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

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

 

풀이 

1) 재귀 활용 문제 

2) 색종이 9분할로 할 때, 각 배열의 크기는 가로 세로 n/3 씩 줄어든다. 즉 n->n/3->n/9 이런식으로 나눠진다. 

 

코드 

public class B_1780 {
	static private int[][] borad;
	static int n_1=0, n0=0, n1=0;
	private static void func(int n, int b1, int b2) {	
    	/* 배열안에 같은 값이 들어가있는지 확인하는 부분 */
		boolean isOk = true;
		int a = borad[b1][b2];
		for (int i = b1; i < n+b1; i++) {
			for (int j = b2; j < n+b2; j++) {
				if (a != borad[i][j]) {
					isOk = false;
					break;
				}
				a = borad[i][j];
			}
			if (!isOk) break;
		}
		
		if (!isOk) { //같은 값이 안들어가있다면
			for (int i = 0; i < 3; i++) {
				for (int j = 0; j < 3; j++) {
					func(n/3, b1 + i*n/3, b2 + j*n/3); //9분할 코드 
				}
			}
		} else {
			if (borad[b1][b2] == 0) n0++;
			else if (borad[b1][b2] == -1) n_1++;
			else if (borad[b1][b2] == 1) n1++;
			return;
		}
		
	}
	public void work() throws IOException { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		borad = new int[n][n];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < n; j++) {
				borad[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		func(n, 0, 0);
		System.out.println(n_1);
		System.out.println(n0);
		System.out.println(n1);
	}
}