문제

백준 2671번
https://www.acmicpc.net/problem/2630

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

---

생각하기

분할 정복의 개념을 익힐 수 있는 문제이다.

동작

크기가 8이라고 했을 때, 4 -> 2 -> 1 형식으로 쪼개지는게 힌트이다.

1사분면과 2사분면 3사분면 4사분면 등의 구간으로 나누는 과정이 결국 분할 정복인데,
이 분할의 구현을 재귀로 만들면 된다.

일단 입력과 같은 배열을 arr에 담아주고 시작한다.

		if(colorCheck(row, col, size)) {
			if(board[row][col] == 0) {
				white++;
			}
			else {
				blue++;
			}
			return;
		}

		int newSize = size / 2;	// 절반 사이즈
		// 재귀 호출
		partition(row, col, newSize);						// 2사분면
		partition(row, col + newSize, newSize);				// 1사분면
		partition(row + newSize, col, newSize);				// 3사분면
		partition(row + newSize, col + newSize, newSize);	// 4사분면
	}

처음에 실행하면 전체가 같은 색깔인지 검사를 먼저하게된다.

colorCheck() 메소드를 통해서 해당 사이즈 배열의 전체를 탐색해서 색상이 같은지 파악한다.
이 함수를 사용해서 각 배열의 색상을 파악하게 된다.

재귀의 탈출조건은 1이다. 1이되면 어쨋든 색깔을 둘 중에 하나는 선택하게 될테니 무조건 return이 될거기 때문이다.

그리고 기존에 있던 사이즈를 절반으로 줄이는 newSize를 새로운 size로 해서 계속해서 크기를 줄여나가면 된다.

---

코드

import java.io.*;
import java.util.*;


public class Main {

	public static int white = 0;
	public static int blue = 0;
	public static int[][] board;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());

		board = new int[N][N];

		StringTokenizer st;

		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");

			for(int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		partition(0, 0, N);

		System.out.println(white);
		System.out.println(blue);

	}

	public static void partition(int row, int col, int size) {

		if(colorCheck(row, col, size)) {
			if(board[row][col] == 0) {
				white++;
			}
			else {
				blue++;
			}
			return;
		}

		int newSize = size / 2;	// 절반 사이즈
		// 재귀 호출
		partition(row, col, newSize);						// 2사분면
		partition(row, col + newSize, newSize);				// 1사분면
		partition(row + newSize, col, newSize);				// 3사분면
		partition(row + newSize, col + newSize, newSize);	// 4사분면
	}


	// 현재 파티션의 컬러가 같은지 체크한다.
	public static boolean colorCheck(int row, int col, int size) {

		int color = board[row][col];	// 첫 번째 원소를 기준으로 검사

		for(int i = row; i < row + size; i++) {
			for(int j = col; j < col + size; j++) {
				// 색상이 같이 않다면 false를 리턴 
				if(board[i][j] != color) {
					return false;
				}
			}
		}
		// 검사가 모두 통과했다는 의미이므로 true 리턴
		return true;
	}
}