[2630] 색종이 만들기_java

분할정복 문제

 

배열의 크기 n인 배열 arr을 받아 0 또는 1로 채워져있는지 확인

-> 아니라면 1/4로 쪼개어서 재차확인

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

public class Main {
	//result[0]은 0으로 채워진 부분색종이 개수, result[1]은 1로 채워진 부분색종이 개수
	static int[] result = new int[2];

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

		int n = Integer.parseInt(br.readLine());
		int[][] arr = new int[n][n];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		check(arr, n);

		System.out.print(result[0] + "\n" + result[1]);

	}
	//n*n 배열 arr과 배열의 크기인 n
	public static void check(int[][] arr, int n) {
		int[][] zero = new int[n][n];
		int[][] one = new int[n][n];
		for (int[] line : one) {
			Arrays.fill(line, 1);
		}

		if (Arrays.deepEquals(arr, zero)) {
			result[0]++;
			return;
		} else if (Arrays.deepEquals(arr, one)) {
			result[1]++;
			return;
		}
		if (n == 1) {
			return;
		}

		check(seperate(arr, 0, 0, n), n / 2);
		check(seperate(arr, n / 2, 0, n), n / 2);
		check(seperate(arr, 0, n / 2, n), n / 2);
		check(seperate(arr, n / 2, n / 2, n), n / 2);

		return;
	}
	//n*n 배열 arr와 시작점(x,y), 배열의 크기 n
	public static int[][] seperate(int[][] arr, int x, int y, int n) {
		int[][] arr_sep = new int[n / 2][n / 2];

		for (int i = 0; i < n / 2; i++) {
			for (int j = 0; j < n / 2; j++) {
				arr_sep[i][j] = arr[i + x][j + y];
			}
		}

		return arr_sep;
	}
}

ㅇ