백준_색종이 만들기_2630

//알고리즘

1. 분할정복

2. 매번 1/4 로 줄어들기 때문에 각 구역을 분할하여  하나씩 처리해야 함.

3. boolean 으로 blue와 white를 각각 체크하여 개수를 더해줌

 

 

package baekjoon;

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

public class 색종이만들기_2630 {
	static int N, map[][], AnsW, AnsB;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());

		map = new int[N][N];
		for (int i = 0; i < map.length; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < map[i].length; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}

		}

//		print(map);
		div(0, 0, 0, N);
		System.out.println(AnsW);
		System.out.println(AnsB);

	}

	private static void div(int idx, int r, int c, int size) {
		boolean isOkB = true;
		boolean isOkW = true;
		L: for (int i = r; i < r + size; i++) {
			for (int j = c; j < c + size; j++) {
				if (map[i][j] != 1) {
					isOkB = false;
					break L;
				}
			}
		}

		L: for (int i = r; i < r + size; i++) {
			for (int j = c; j < c + size; j++) {
				if (map[i][j] != 0) {
					isOkW = false;
					break L;
				}
			}
		}
		if (isOkB) {
			AnsB++;
			return;
		}
		if (isOkW) {
			AnsW++;
			return;
		}

		int num = size / 2;
		div(idx + 1, r, c, num);
		div(idx + 1, r, c + num, num);
		div(idx + 1, r + num, c, num);
		div(idx + 1, r + num, c + num, num);
	}

	private static void print(int[][] map) {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}

}