백준 2630

문제

---

Code

package test;

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

public class P2630 {

	static int[][] board;

	static int whiteCount; // 하얀색 색종이 개수
	static int blueCount; // 파란색 색종이 개수

	static final int WHITE = 0;
	static final int BLUE = 1;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		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());
			}
		}
		
		partition(0, 0, N);
		
		StringBuilder sb = new StringBuilder();
		sb.append(whiteCount).append('\n').append(blueCount);
		bw.write(sb.toString());
		
		br.close();
		bw.flush();
		bw.close();
		
		
	}
    /*
    boolean sameColor(int row, int col, int size)
    
	가장 왼쪽 상단의 모서리가 row열, col 행이고 한 변의 길이가 size일 때
    해당 모양의 색종이가 모두 같은 색인지 판별
	*/
	private static boolean sameColor(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(board[i][j] != color) {
					return false;
				}
			}
		}
		return true;
	}

 	/*
    void partition(int row, int col, int size)
    
	가장 왼쪽 상단의 모서리가 row열, col 행이고 한 변의 길이가 size일 때
    
    1) 해당 모양의 색종이가 모두 같은 색 -- > 정복, 분할 종료
    2) 해당 모양의 색종이 중 다른색 존재 -- > 4등분으로 분할 후 재귀 탐색
	*/
	private static void partition(int row, int col, int size) {
    	// 1) 해당 모양의 색종이가 모두 같은 색 
		if(sameColor(row, col, size)) {
			if(board[row][col] == WHITE) {
				whiteCount++;
			} else {
				blueCount++;
			}
            // 정복 (분할 종료)
			return;
		}
        
        // 2) 해당 모양의 색종이 중 다른색 존재
		
		int nextSize = size / 2;
		
		partition(row, col, nextSize);
		partition(row, col + nextSize, nextSize);
		partition(row + nextSize, col, nextSize);
		partition(row + nextSize, col + nextSize, nextSize);
	}
}

---

참고 : https://st-lab.tistory.com/227