[백준(Baekjoon)][자바(java)] 2630 : 색종이 만들기 / 분할 정복

 

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

2630번: 색종이 만들기

 

< 문제의 포인트 >

 

* 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다.

* 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

 

 

< 문제 풀이 >

 

시작점 : x = 0, y = 0

길이 : len = n

n*n의 배열을 (x, y)부터 len*len 만큼 루프를 돌아 탐색하며

시작점의 색종이 색과 나머지 다른 색종이 색이 모두 같은지 판별

다르면? 루프에서 빠져나와 (len/2)*(len/2) 크기 네 개로 나누어 recursion  ( len이 0이면 recursion 종료 -- base case )

같으면? 0일 경우 흰 색종이 개수 +1, 1일 경우 파란 색종이 개수 +1

 

import java.util.Scanner;

public class Main {
	
	static int p[][], w, b; 	// paper arr, white, blue
	
	public static void cntColor( int x, int y, int len ) {
		if( len == 0 )
			return;
		boolean isDiff = false;
		for( int i = x; i < x+len; i++ ) {
			for( int j = y; j < y+len; j++ ) {
				if( p[x][y] != p[i][j] ) {
					isDiff = true;
					break;
				}
			}
 		}
		if( isDiff ) {
			cntColor( x, y, len/2 );
			cntColor( x, y+len/2, len/2 );
			cntColor( x+len/2, y, len/2 );
			cntColor( x+len/2, y+len/2, len/2 );
		}
		else {
			if( p[x][y] == 0 )	w++;
			else				b++;
		}
	}

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		p = new int[n][n];
		for( int i = 0; i < n; i++)
			for( int j = 0; j < n; j++ )
				p[i][j] = sc.nextInt();
		sc.close();
		
		cntColor( 0, 0, n );
		
		System.out.println( w + "\n" + b );
	}

}