[백준 1780번] 종이의 개수- java

문제 설명

1. N이 주어진다.

2. NxN배열에 해당하는 종이들이 -1, 0, 1로 주어진다.

3. 한 범위의 모든 종이들이 해당 숫자로 이루어진 경우들을 구한다.

4. 범위는 전체 크기 사이즈를 가로세로를 3으로 나눈 총 9개의 범위로 이루어져 있고, 해당 범위에 다른 종이가 있으면 다시 나누어 준다.

5. -1, 0, 1 각각 얼마나 많은 '범위'가 존재하는지 구하면 된다.

풀이 과정

 1. 분할 정복 문제이다.

 2. 값들을 더 작은 수로 나누고, 그곳에서부터 조합해 맞추어 나가면 된다.

 3. 이전 글의 쿼드 트리와 유사한 문제이다. 그냥 범위를 더 잘게 나누고, 괄호를 없애면 된다.

 4. 전체 범위에 대해 다른 숫자가 존재하는지 판단하고, 있으면 더 잘게 나누고 없으면 지금 숫자를 해당 배열에 더해주면 된다.

 5. -1, 0, 1세가지 숫자들이 차례로 return되면 되니까 0, 1, 2배열에 1씩 더해서 더해주면 된다.

코드

import java.util.Scanner;

public class Main {
	public static int paper[][];
	public static int N;
	public static int ans[] = new int[3];
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		
		paper = new int[N][N];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				paper[i][j] = sc.nextInt();
			}
		}
		QT(0, 0, N);
		for(int i=0; i<3; i++)System.out.println(ans[i]);
	}
	public static void QT(int x, int y, int size) {
		int nowNum = paper[x][y];
		if(allSame(x, y, size, nowNum)) {
			ans[nowNum+1]++;	// 해당 숫자는 -1, 0, 1로이루어지는데, 배열은 0, 1, 2이니까 1을 더해서 ++연산 시행
			return;
		}
		int changeSize = size/3;	// 모든 분할정복 9가지 경우의 수
		QT(x, y, changeSize);
		QT(x+changeSize, y, changeSize);
		QT(x+changeSize*2, y, changeSize);
		QT(x, y+changeSize, changeSize);
		QT(x, y+changeSize*2, changeSize);
		QT(x+changeSize, y+changeSize, changeSize);
		QT(x+changeSize*2, y+changeSize, changeSize);
		QT(x+changeSize, y+changeSize*2, changeSize);
		QT(x+changeSize*2, y+changeSize*2, changeSize);
		
	}
	public static boolean allSame(int x, int y, int size, int nowNum) {
		for(int i=x; i<x+size; i++) {
			for(int j=y; j<y+size; j++) {
				if(nowNum != paper[i][j]) {
					return false;
				}
			}
		}
		return true;
	}
}