백준 - 1780번 - 종이의 개수

1780번

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

public class Main {
	static int[][] board;
	static int GRAY = 0;
	static int WHITE = 0;
	static int BLACK = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(bf.readLine());
		board = new int[n][n];
		StringTokenizer st;

		for (int i = 0; i<n; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j = 0; j<n; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		partition(0, 0, n);

		System.out.println(GRAY);
		System.out.println(WHITE);
		System.out.println(BLACK);
	}

	static void partition(int row, int col, int size) {
		if (colorCheck(row, col, size)) {
			if (board[row][col] == -1) {
				GRAY++;
			}
			else if (board[row][col] == 0) {
				WHITE++;
			}
			else {
				BLACK++;
			}

			return;
		}

		int newSize = size / 3;

		partition(row, col, newSize);
		partition(row, col + newSize, newSize);
		partition(row, col + 2 * newSize, newSize);

		partition(row + newSize, col, newSize);
		partition(row + newSize, col + newSize, newSize);
		partition(row + newSize, col + 2 * newSize, newSize);

		partition(row + 2 * newSize, col, newSize);
		partition(row + 2 * newSize, col + newSize, newSize);
		partition(row + 2 * newSize, col + 2 * newSize, newSize);
	}

	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++) {
				if (color != board[i][j]) {
					return false;
				}
			}
		}
		return true;
	}


}

풀이

---

9개로 나눠진 분면이 있다. 각 9개의 분면마다 같은 숫자로 되어있으면 1개로 친다. 아니라면 그 분면을 또 9개로 나눈다. 같은 숫자로 되었있다면 1개 아니면 또 나누다. 이런식으로 계속해서 흰색, 회색, 검정이 각각 몇개인지 구하는 문제다.

분할정복을 사용하는것이 문제의 핵심이다.

먼저 2차원 배열로 n x n 만큼 입력을 받는다.

분할정복 메서드를 하나 만든다.
먼저 (0, 0, n) 을 받아서 전체가 하나의 숫자로 되어있는지 확인하고 아니라면

		partition(row, col, newSize);
		partition(row, col + newSize, newSize);
		partition(row, col + 2 * newSize, newSize);

		partition(row + newSize, col, newSize);
		partition(row + newSize, col + newSize, newSize);
		partition(row + newSize, col + 2 * newSize, newSize);

		partition(row + 2 * newSize, col, newSize);
		partition(row + 2 * newSize, col + newSize, newSize);
		partition(row + 2 * newSize, col + 2 * newSize, newSize);

위와 같이 전체를 9개의 분면으로 확인한다. 예를 들어 n이 9면 99이니까 33칸이 9개 있는꼴이다. 그래서 그 칸들마다 같은 숫자로 되어있는지 확인한다.
111
111
111

위의 예시가 같은숫자로 1개로 친다.

1 -1 0
1 -1 0
-1 0 1

위의 예시는 같은숫자로 되어있지 않기 때문에 9개로 분면을 나눠준다.

그러면 하나단위로 쪼개지기 때문에 각각 하나의 숫자로 되어있다고 판단하고 카운트를 해준다.

분할정복 문제를 접해보니 몇가지 포인트가 있어보인다.
1. 재귀를 쓴다.
2. 제일 큰단위부터 확인하고 아니면 그다음 단위해서 제일 작은 단위까지 찍는다. 그 과정에서 개수를 카운팅하거나 횟수를 세거나 하는 느낌이다.