[백준(Baekjoon)][자바(java)] 1780 : 종이의 개수 / 분할 정복

 

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

1780번: 종이의 개수

 

( 쿼드트리와 비슷한데 4개 대신 9개로 나누는 문제 )

 

 

< 문제의 포인트 > 

 

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.

2. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

 

 

< 문제 풀이 >

 

import java.util.Scanner;

public class Main {

	static int arr[][], one_n, zero, one;	// one_n : negative num
	
	public static void cntPaper( int x, int y, int len ) {
		if( len == 0 )
			return;
		boolean isDiff = false;
		loop:
		for( int i = x; i < x+len; i++ ) {
			for( int j = y; j < y+len; j++ ) {
				if( arr[x][y] != arr[i][j] ) {
					isDiff = true;
					break loop;
				}
			}	
		}
		if( isDiff ) {
			cntPaper( x, 		y, 			len/3 );
			cntPaper( x, 		y+len/3, 	len/3 );
			cntPaper( x, 		y+len/3*2, 	len/3 );
			cntPaper( x+len/3, 	y, 			len/3 );
			cntPaper( x+len/3, 	y+len/3, 	len/3 );
			cntPaper( x+len/3, 	y+len/3*2, 	len/3 );
			cntPaper( x+len/3*2, y, 		len/3 );
			cntPaper( x+len/3*2, y+len/3, 	len/3 );
			cntPaper( x+len/3*2, y+len/3*2, len/3 );
		}
		else {
			int t = arr[x][y];
			if( t == -1 ) 		one_n++;
			else if( t == 1 ) 	one++;
			else if( t == 0 ) 	zero++;
		}
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		arr = new int[n][n];
		for( int i = 0; i < n; i++ )
			for( int j = 0; j < n; j++ )
				arr[i][j] = sc.nextInt();
		cntPaper( 0, 0, n );
		System.out.println( one_n + "\n" + zero + "\n" + one );
		sc.close();
	}
}