[1780] 백준 - 종이의 개수(JAVA)

- answer {-1, 0, 1로 이루어진 종이 수를 저장 }

- 한 변의 길이를 N으로 하는 종이를 (1,1)부터 탐색 => search(시작r, 시작c, 한변길이N)

- 같은 숫자로 이루어졌는지 탐색 => checkNum(시작r, 시작c, 한변길이n)

(r, c) ~ (r+n-1, c+n-1)의 배열 안이 모두 같은 수로 이루어져있는지 검사
   - pivot : 배열의 첫 좌표
                : 배열 속 다른 값들이 모두 이 값과 같으면, 같은 수로 이루어진 종이임
   - isSame : 같은 수로 이루어져 있으면 true, 아니면 false

- checkNum이 true면, 같은 값으로 이루어져있는 종이이므로, answer[num+1]++

num = -1 이면, answer[0]++
num = 0 이면, answer[1]++
num = 1 이면, answer[2]++

- 다른 값으로 이루어져있으면, 종이를 9등분하여 다시 탐색

- 한 변의 길이인 N을 N/3한 새로운 변의 길이를 newNum으로 한다.
- 탐색할 시작 점인 (r, c)는 아래 그림과 같이 한다.
          search(r, c, newNum);
          search(r, c + newNum, newNum);
          search(r, c + 2 * newNum, newNum);
          search(r + newNum, c, newNum);
          search(r + newNum, c + newNum, newNum);
          search(r + newNum, c + 2 * newNum, newNum);
          search(r + 2 * newNum, c, newNum);
          search(r + 2 * newNum, c + newNum, newNum);
          search(r + 2 * newNum, c + 2 * newNum, newNum);

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	static int N, paper[][], answer[];
 
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
 
		// 입력
		paper = new int[N + 1][N + 1];
		for (int i = 1; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				paper[i][j] = Integer.parseInt(st.nextToken());
			}
		}
 
		answer = new int[3]; // { -1, 0, 1로 채워진 수 개수 }
		search(1, 1, N);
 
		// -1, 0, 1로 이루어진 종이 수 출력
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < 3; i++)
			sb.append(answer[i] + "\n");
		System.out.println(sb.toString());
	}
 
	// 종이개수 구하기
	private static void search(int r, int c, int n) {
		if (n < 1) // 종료조건
			return;
 
		// 같은 숫자로 채워져있으면, 종이 개수 세기
		if (checkNum(r, c, n)) {
			int num = paper[r][c];
			answer[num + 1]++;
			return;
		}
 
		// 다른 숫자
		int newNum = n / 3;
		search(r, c, newNum);
		search(r, c + newNum, newNum);
		search(r, c + 2 * newNum, newNum);
		search(r + newNum, c, newNum);
		search(r + newNum, c + newNum, newNum);
		search(r + newNum, c + 2 * newNum, newNum);
		search(r + 2 * newNum, c, newNum);
		search(r + 2 * newNum, c + newNum, newNum);
		search(r + 2 * newNum, c + 2 * newNum, newNum);
	}
 
	// 같은 숫자로 채워져있는지 확인
	private static boolean checkNum(int r, int c, int n) {
		int nr = r + n - 1;
		int nc = c + n - 1;
 
		int pivot = paper[r][c]; // 첫 좌표 값을 기준으로하여 비교
		boolean isSame = true;
		for (int i = r; i <= nr && isSame; i++) {
			for (int j = c; j <= nc && isSame; j++) {
				if (pivot != paper[i][j]) // 하나라도 다르면 false
					isSame = false;
			}
		}
 
		return isSame;
	}
 
}