[분할정복] 백준 - 종이의 개수

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

1780번: 종이의 개수

 

 

-문제해설

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

위 블로그 내용 참고

 

전형적인 분할정복 문제인데 분할정복을 for문을 이용해서 하려다가 구현하지 못해서 다른 분의 블로그를 참고해서 그냥 반복문 사용을 하지 않고 풀었다. ㅎㅎ

 

먼저 처음의 종이의 (0, 0)의 값과 전체값이 똑같은지 확인하기 위해 colChk() 메소드를 통해서 확인하고 같은 경우

-1, 0, 1 중에 어떤 값인지 확인하고 출력값인 -1, 0, 1의 개수를 저장하는 변수를 1 증가시킨다.

 

만약에 전체값의 색깔이 다르다면 종이를 총 9등분해서 

(1, 1)부분부터 (3, 3) 부분까지 check메소드를 재귀 호출한다.

 

 

-자바

package bfs_dfs;

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

public class BJ1780 {
	private static int[][] arr;
	private static int a, b, c;
	
	private static void check( int row, int col, int size ) {
		if( colChk( row, col, size ) ) {
			if( arr[row][col] == -1 ) a++;
			else if( arr[row][col] == 0 ) b++;
			else c++;
			return;
		}
		int newSize = size/3;
		
		check( row, col, newSize );						//(1, 1)
		check( row, col+newSize, newSize );				//(1, 2)
		check( row, col+2*newSize, newSize );			//(1, 3)
		
		check( row+newSize, col, newSize );				//(2, 1)
		check( row+newSize, col+newSize, newSize );		//(2, 2)
		check( row+newSize, col+2*newSize, newSize );	//(2, 3)
		
		check( row+2*newSize, col, newSize );			//(3, 1)
		check( row+2*newSize, col+newSize, newSize );	//(3, 2)
		check( row+2*newSize, col+2*newSize, newSize);	//(3, 3)
	}
	
	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( color != arr[i][j] ) return false;
			}
		}
		return true;
	}

	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() );
		}
		check( 0, 0, n );
		
		System.out.println( a + "\n" + b + "\n" + c );
	}
}

 

 

-파이썬

from sys import stdin
a = b = c = 0
input = stdin.readline
n = int( input().rstrip() )
arr = []
for _ in range( n ):
    tmp = list( map(int, input().rstrip().split()) )
    arr.append( tmp )

def cntPaper( row, col, size ):
    global a, b, c
    if chkColor( row, col, size ):
        if arr[row][col] == -1: a += 1
        elif arr[row][col] == 0: b += 1
        else: c += 1
        return
    
    newSize = size//3
    
    cntPaper( row, col, newSize )
    cntPaper( row, col+newSize, newSize )
    cntPaper( row, col+2*newSize, newSize )

    cntPaper( row+newSize, col, newSize )
    cntPaper( row+newSize, col+newSize, newSize )
    cntPaper( row+newSize, col+2*newSize, newSize )
    
    cntPaper( row+2*newSize, col, newSize )
    cntPaper( row+2*newSize, col+newSize, newSize )
    cntPaper( row+2*newSize, col+2*newSize, newSize )
        
def chkColor( row, col, size ):
    color = arr[row][col]
    for i in range( row, row+size ):
        for j in range( col, col+size ):
            if color != arr[i][j]: return False
    return True

cntPaper( 0, 0, n )
print( a ); print( b ); print( c )