백준 1780번

종이의 개수

문제

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

출력

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

예제

알고리즘 분류

• 분할 정복
• 재귀

코드

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

public class Main {
	public static int board[][];
	public static int minus = 0;
	public static int zero = 0;
	public static int plus = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		board = new int[N][N];
		
		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());
		}
		
		split(0, 0, N);
		
		System.out.println(minus);
		System.out.println(zero);
		System.out.println(plus);
	}
	
	public static void split(int row, int col, int size) {
		if(check(row, col, size)) {
			if(board[row][col] == -1)
				minus++;
			else if(board[row][col] == 0)
				zero++;
			else
				plus++;
			
			return;
		}
		
		int temp = size / 3;
		
		split(row, col, temp);
		split(row+temp, col, temp);
		split(row+temp+temp, col, temp);
		split(row, col+temp, temp);
		split(row+temp, col+temp, temp);
		split(row+temp+temp, col+temp, temp);
		split(row, col+temp+temp, temp);
		split(row+temp, col+temp+temp, temp);
		split(row+temp+temp, col+temp+temp, temp);
	}
	
	public static boolean check(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분할로 재귀를 반복하는 방식이다. 방법의 큰 그림 자체는 그리기 쉬웠는데 세세한 부분을 그리는 것이 어려웠다. 인터넷을 활용하여 깨달은 것은, 딱히 효율적인 방법이 있다기 보다는, 단순하게 재귀를 반복해서 해결하는 문제인듯 하다.