BOJ_S2_1780

📁 [S2_1780] 종이의 개수

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


public class Main {
	static StringTokenizer st;
	static int[][] arr;
	static int[] color;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 행렬의 크기 
		int N = Integer.parseInt(br.readLine());
		
		arr = new int[N][N];
		
		// -1, 0, 1 
		color = new int[3]; 
		
		// 배열 입력
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		partition(0,0,N);
		
		
		for(int i=0; i<3; i++) {
			System.out.println(color[i]);
		}
	}
	
	
	static void partition(int row, int col, int size) {
		// 종이가 다 같은 색이면
		if(check(row, col, size)) {
		
			if(arr[row][col] == -1) {
				color[0]++;
			}
			else if(arr[row][col] == 0) {
				color[1]++;
			}
			else {
				color[2]++;
			}
			return;
		}
		
		// 다 다른색이면 9 등분
		
		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 check(int row, int col, int size) {
		int first = arr[row][col];
		for(int i=row; i<row+size; i++) {
			for(int j=col; j<col+size; j++) {
				if(first != arr[i][j]) {
					return false;
				}
			}
		}
		return true;
	}
}

🤔 나의 생각

9등분을 하여 계속 구해내는 것을 보고 재귀가 떠올랐다.
그래서 종이안에 숫자가 다 같은 색인지 알아내는 메서드 하나 , 전체를 돌면서 같은 색이면 각 숫자의 개수를 카운팅 해주고 다른 색이면 9등분하여 재귀를 돌렸다.
이런 문제는 분할을 잘 이용해야 하는 것 같다. 재귀를 돌리면 보통 하나의 재귀 호출문으로 생각하는데 분할 문제는 분할하는 개수만큼 재귀 호출문을 사용해야해서 알고 있지 않으면 생각해내기 어려운 것 같다.
그리고 재귀 호출할 때 새로운 사이즈를 N이 3의 배수니까 3을 나눠주는 것도 중요하다.
실버2 였지만 분할에 대해 미숙하여 시간이 좀 걸렸다..
그리고 제일 처음에는 9분할을 못보고 달라지면 분할해야되는 것을 생각하다 너무 어려운데 하고 보니 9분할 이였따.. ㅋㅋ
좀 더 집중 하자 !!