[분할정복] 백준 - 색종이 만들기

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

2630번: 색종이 만들기

 

 

-문제해설

 

풀다가 어려워서 이 분의 코드를 참고했다.

https://st-lab.tistory.com/227

 

먼저 문제와 나와있는 대로 정사각형에 모든 값이 1이 아니거나 0이 아니면 현재 정사각형을 2등분해서 각 사분면에 대해서 다시 전체 값이 1인지 0인지를 검사한다. 이때 전체값이 1이거나 0이면 재귀함수를 빠져나오고 아닐 경우 재귀함수를 계속 호출한다.

 

아직 분할정복에 대해서 공부가 더 필요함을 느꼈다...!

 

 

 

 

-자바

package bfs_dfs;

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

public class BJ2630 {
	private static int white = 0;
	private static int blue = 0;
	private static int[][] arr;
	
	private static boolean colChk( int row, int col, int size ) {
		int color = arr[row][col];
		
		for( int i=row; i<row+size; i++ ) {
			for( int j=col; j<col+size; j++ ) {
				if( arr[i][j] != color ) return false;
			}
		}
		
		return true;
	}

	private static void cutPaper( int row, int col, int size ) {
		if( colChk( row, col, size ) ) {
			if( arr[row][col] == 0 ) white++;
			else blue++;
			
			return;
		}
		
		int newSize = size / 2;
		cutPaper(row, col, newSize);
		cutPaper(row, col+newSize, newSize);
		cutPaper(row+newSize, col, newSize);
		cutPaper(row+newSize, col+newSize, newSize);
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt( br.readLine() );
		
		StringTokenizer st;
		arr = new int[n][n];
		for( int i=0; i<n; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( int j=0; j<n; j++ ) arr[i][j] = Integer.parseInt( st.nextToken() );
		}
		
		cutPaper(0, 0, n);
		
		System.out.println( white );
		System.out.println( blue );
		
		
		
	}
}

 

-파이썬