[백준 : 2630] 색종이 만들기 - 분할정복

 

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

public class Main {
	public static int N;
	public static int map[][];
	public static int wb[] = new int[2];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		map = new int[N][N];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		solution(0, 0, 0);
		System.out.println(wb[0]);
		System.out.println(wb[1]);
	}

	public static void solution(int x, int y, int depth) {
		int length = (int) (N / Math.pow(2, depth));
		int color = map[x][y];
		boolean isSame = true;
		loop: for (int i = 0; i < length; i++) {
			for (int j = 0; j < length; j++) {
				if (color != map[x + i][y + j]) {
					isSame = false;
					break loop;
				}
			}
		}

		if (isSame) {
			wb[color]++;
			return;
		}

		solution(x, y, depth + 1);
		solution(x + length / 2, y, depth + 1);
		solution(x, y + length / 2, depth + 1);
		solution(x + length / 2, y + length / 2, depth + 1);

	}
}