[BAEKJOON] 색종이 만들기

---

분할 정복 방법으로 접근해야 하는 문제이다.

흰색과 파란색 정사각형 색종이의 개수를 각각 알아내어야 하는데 만약 1/2씩 접었을 때 나뉘어진 영역을 모두 같은 색상이어야 더 이상 나뉘지 않음을 알 수 있다.

만약 나뉜 영역이 오로지 한 색상만을 가지고 있지 않다면 다시 1/2씩 접혔다는 것을 의미한다.

아래 이미지와 같이 전체 붉은 영역이 한 색상만을 가지고 있지 않으므로 4등분으로 분할하고,

나뉜 부분 색종이를 하나씩 떼어 보았을 때에도 한 색상만을 가지고 있지 않다면 4등분, 한 색상을 유지한다면 현재 색상의 카운트를 증가시켜 return한다. 

이렇게 반복하다보면 흰색, 파란색의 색종이의 개수를 카운트 하며, 모두 같은 색상인 가장 작은 단위의 색종이를 마지막으로 return될 것이다.

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

public class Main {
	static int N, arr[][];
	static int white, blue;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		N = Integer.parseInt(br.readLine());
		arr = new int[N][N];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		recur(0, 0, N);
		sb.append(white+"\n").append(blue+"");
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
	private static void recur(int x, int y, int size) {
		if(check(x, y, size)) {
			if(arr[x][y] == 0) white++;
			else blue++;
			return;
		}
		int half = size/2;
		recur(x, y, half);
		recur(x+half, y, half);
		recur(x, y+half, half);
		recur(x+half, y+half, half);
	}
	private static boolean check(int x, int y, int size) {
		int color = arr[x][y];
		for(int i=x; i<x+size; i++) {
			for(int j=y; j<y+size; j++) {
				if(arr[i][j] != color) return false;
			}
		}
		return true;
	}
}

[출처]

https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기