[백준 1780] 종이의 개수(Java)

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

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로만 채워진 종이의 개수를 출력한다.

풀이 설명

1. 현재 종이가 하나의 숫자로만 이루어져 있는지 검사하는 check함수를 선언하고, 한 변의 길이와 시작 인덱스를 매개     변수로 넘긴다.

  1-1. 현재 종이의 전체 칸을 탐색하면서 하나라도 다른 수가 있다면 isChange에 체크하고, break한다.

  1-2. isChange에 체크가 되었다면, 현재 종이를 9등분하여 다시 검사해야 한다.

    1-2-1. 현재 한 변의 길이 len을 3등분하고, 9등분한 각 칸의 시작 인덱스를 매개변수로 해서 check를 재귀호출한다.

  1-3. isChange에 체크가 되어있지 않다면, 현재 종이의 숫자에 따라 -1, 0, 1에서 일치하는 변수를 1 올린다.

  1-4. 만약 현재 변의 길이가 1이라면, 더 이상 나눌 수 없으므로, 현재 칸의 숫자에 따라 -1, 0, 1에서 일치하는 변수를            1 올린다.

Java 코드

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

public class Main {
	
	static int len;
	static int[][] paper;
	static int minus;
	static int zero;
	static int plus;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		len = Integer.parseInt(br.readLine());
		paper = new int[len][len];
		
		for(int i=0; i<len; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<len; j++) {
				paper[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		check(len, 0, 0);
		System.out.println(minus);
		System.out.println(zero);
		System.out.println(plus);
	}
	
	public static void check(int len, int x, int y) {
		if(len == 1) {
			if(paper[x][y] == -1) minus++;
			else if(paper[x][y] == 0) zero++;
			else plus++;
			return;
		}
		
		boolean isChange = false;
		int first = paper[x][y];
		for(int i=0; i<len; i++) {
			for(int j=0; j<len; j++) {
				if(paper[x+i][y+j] != first) {
					isChange = true;
					break;
				}
			}
		}
		
		int nextLen = len/3;
		if(isChange) {
			check(nextLen, x, y);
			check(nextLen, x, y + nextLen);
			check(nextLen, x, y + nextLen * 2);
			check(nextLen, x + nextLen, y);
			check(nextLen, x + nextLen, y + nextLen);
			check(nextLen, x + nextLen, y + nextLen * 2);
			check(nextLen, x + nextLen * 2, y);
			check(nextLen, x + nextLen * 2, y + nextLen);
			check(nextLen, x + nextLen * 2, y + nextLen * 2);
		}else {
			if(first == -1) minus++;
			else if(first == 0) zero++;
			else plus++;
		}
	}
}