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

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

2630번: 색종이 만들기

코드설명

분할 정복 문제입니다.

 

 

N문제로직입니다.

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

2. 처음에 각 Size N 만큼 해당 정사각형이 하나의 색종이로 이루어져있는지 확인합니다.

만약 해당 정사각형이 하나의 색종이로 이루어졌다면 1개만 세고 종료시킵니다.

아니라면, 해당 정사각형을 아래와 같이 4사분면을 나누어서 모두 호출합니다.

int nSize = size / 2; //절반씩 줄여나갑니다.
//각 4분면 나누어서 처리
divideConquer(r, c, nSize);
divideConquer(r, c + nSize , nSize);
divideConquer(r + nSize, c, nSize);
divideConquer(r + nSize, c + nSize, nSize);

 

위의 2번 로직을 계속해서 반복하면됩니다.

 

설명은 코드에 주석으로 담아두었습니다.

 

코드

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

public class Main {
	public static int N, M;
	public static int[][] map;
	public static int answer = 0, answerWhite = 0, answerBlue = 0;
	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(answerWhite);
    	System.out.println(answerBlue);
    	
    	
    }
	public static void divideConquer(int r, int c, int size) {
		
		boolean flag = true; //처음에는 true로 초기화. 이후에 false로 바뀌어있다면, 해당 사각형은 분할정복의 필요성이 존재.
		int standardColor = map[r][c];
		for(int i=r; i<r + size;i++) {
			for(int j=c; j<c + size;j++) {
				//색상이 같지 않다면 false
				if(map[i][j] != standardColor) {
					flag = false;
					break;
				}
			}
		}
		
		if(flag == true) {
			if(map[r][c] == 0) {
				answerWhite += 1;
			}else if(map[r][c] == 1){
				answerBlue += 1;
			}
			return ;
		}
		
		int nSize = size / 2; //절반씩 줄여나갑니다.
		//각 4분면 나누어서 처리
		divideConquer(r, c, nSize);
		divideConquer(r, c + nSize , nSize);
		divideConquer(r + nSize, c, nSize);
		divideConquer(r + nSize, c + nSize, nSize);
		
	}

}