[백준] 2630번 색종이 만들기

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

2630번: 색종이 만들기

목표 : 정사각형 모양의 색종이에서 하얀색 색종이와 파란색 색종이의 개수를 구하기, 단 전체 종이가 모두 같은 색으로 칠해져 있어야하고 그렇지 않다면 정사각형을 더 이상 자를 수 없을 때 까지 N/2 * N/2 색종이로 나눈다. 분할과 정복 활용, 재귀 div함수 map[x][y]가 1인(파란색)의 갯수를 세고 갯수가 0 이면 하얀색 갯수 누적, 갯수가 N^2 이면 파란색 갯수 누적 둘다 아니면, 4개의 문제 재귀 주의 : 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 기준으로 분할하여 N/2로 재귀 -> 쿼드 트리

import java.util.Arrays;
import java.util.Scanner;

public class Main{
	static int[][] map;
	static int N,wcnt=0,bcnt=0;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N =sc.nextInt();
		map = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = sc.nextInt();
			}
		}//end of input
		
		div(0,0,N);
		System.out.println(wcnt);
		System.out.println(bcnt);
	
	}

	public static void div(int x, int y, int N) {
		//먼저 맵에 1으로 가득찼는지 검사
		int count = 0;
		for (int i = x; i < x+N; i++) {
			for (int j = y; j < y+N; j++) {
				if(map[i][j]==1)count++;
			}
		}
		//갯수가 0 이면 wcnt++
		if(count == 0)wcnt++;
 		//갯수가 1이면 bcnt++
		else if(count == N*N)bcnt++;
		//둘다 아니면 재귀 1,2,3,4 분할하여 재귀
		else {
			div(x,y,N/2);
			div(x,y+N/2,N/2);
			div(x+N/2,y,N/2);
			div(x+N/2,y+N/2,N/2);
		}
		
	}
}