[백준] 1780 종이의 개수 - 분할정복 + 재귀 JAVA

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

1780번: 종이의 개수

코드설명

N문제로직입니다.

1. 분할정복을 위한 재귀를 사용합니다.

2. 분할 정복 함수(divideConquer):
      3. 먼저 해당 영역이 모두 같은 숫자로 이루어져 있는지 확인합니다. 만약 그렇다면, 해당 숫자에 따라서 minusOneAnswer, zeroAnswer, oneAnswer를 각 이루어진 숫자에 맞게 증가시킵니다.
      4. 만약 해당 영역이 모두 같은 숫자로 이루어져 있지 않다면, 해당 영역을 9개의 작은 부분으로 나누어 각각에 대해 재귀적으로 divideConquer 함수를 호출합니다.

 

코드

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

public class Main {
	public static int N;
	public static int answer = 0;
	public static int[][] map;
	public static int minusOneAnswer = 0, zeroAnswer = 0, oneAnswer = 0;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	map = new int[N][N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<N;j++) {
    			map[i][j] =Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	divideConquer(0, 0, N);
    	System.out.println(minusOneAnswer);
    	System.out.println(zeroAnswer);
    	System.out.println(oneAnswer);
    }
	
	public static void divideConquer(int r, int c, int size) {
		//먼저 전체 공간이 모두 같은 숫자로 되어있는지 확인한다.
		int first = map[r][c];
		boolean flag = true;
		for(int i=r; i<r + size; i++) {
			for(int j=c; j< c + size; j++) {
				if(map[i][j] != first) { //만약 첫번쨰와 다르다면 바로 실패다.
					flag = false;
					break;
				}
			}
		}
		if(flag == true) { //만약 모두 같다면,
			if(first == -1) {
				minusOneAnswer += 1;
			}else if(first == 0) {
				zeroAnswer += 1;
			}else if(first == 1) {
				oneAnswer += 1;
			}
			return ;
		}
		
//		if(size == 1) { // 처음에는 size가 1인경우를 따로처리했지만, 다시 확인해보니 위에서 해당 구문을 이미 처리합니다.
//			if(map[r][c] == -1) {
//				minusOneAnswer += 1;
//			}else if(map[r][c] == 0) {
//				zeroAnswer += 1;
//			}else if(map[r][c] == 1) {
//				oneAnswer += 1;
//			}
//			return ;
//		}
		
		int nSize = size / 3;
		for(int i=r;i<r + size; i+=nSize) {
			for(int j=c; j<c + size; j+=nSize) {
				divideConquer(i, j, nSize);
			}
		}
		
	}
	

	
}