Baekjoon 1780번: 종이의 개수 (분할정복)

www.acmicpc.net/problem/1780

1780번: 종이의 개수

---

앞서 푼 쿼드트리랑 비슷한 문제, 다만 9등분을 하고 -1, 0, 1로 채워져 있어 경우의 수가 더 늘어났다. 이번에는 9등분 하는 부분을 메소드로 넣었다.

 

package BJ;

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

//종이의 개수
public class BJ1780 {
	public static int zero, one, mOne;
	public static int[][] map;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		boolean flag = true;
		map = new int [N][N];
		for (int i = 0; i < N; i++) {
			String tmp = br.readLine();
			String[] sarr = tmp.split(" ");
			for (int j = 0; j < sarr.length; j++) {
				map[i][j] = Integer.parseInt(sarr[j]);
				if(flag && map[i][j] != map[0][0]) flag = false;
			}
		}//end of for
		
		if(!flag) devide(0,0,N/3);
		else {
			if(map[0][0] == 1) one++;
			else if(map[0][0] == 0) zero++;
			else mOne++;
		}
		System.out.println(mOne);
		System.out.println(zero);
		System.out.println(one);
	}//end of main
	
	
	public static void check(int x, int y, int size) {
		int fix = map[x][y];
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				if(map[x+i][y+j] == fix) continue;
				devide(x, y, size/3);
				
				return;
			}
		}
		if(fix == 1) one++;
		else if(fix == -1) mOne++;
		else zero++;
	}
	
	public static void devide(int x, int y, int s) {
		check(x, y, s);
		check(x, y+s, s);
		check(x, y+(2*s), s);
		check(x+s, y, s);
		check(x+s, y+s, s);
		check(x+s, y+(2*s), s);
		check(x+(2*s), y, s);
		check(x+(2*s), y+s, s);
		check(x+(2*s), y+(2*s), s);
	}
}//end of class