[BOJ 2630번] 색종이 만들기

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

2630번: 색종이 만들기

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

public class Main {
	
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static int paper[][];
	static int whitepaper=0;
	static int bluepaper=0;
	
	public static void main(String args[]) throws Exception {
		int num=Integer.parseInt(br.readLine());
		paper=new int[num][num];
		for(int i=0;i<num;i++) {
			String s[]=br.readLine().split(" ");
			for(int j=0;j<num;j++) {
				paper[i][j]=Integer.parseInt(s[j]);
			}
		}
		function(0, 0, num);
		bw.write(whitepaper+"\n"+bluepaper);
		bw.flush();
		bw.close();
	}
	
	static void function(int start_i, int start_j, int n) {
		if(n==1) {
			if(paper[start_i][start_j]==1) bluepaper++;
			else if(paper[start_i][start_j]==0) whitepaper++;
			return;
		}
		int sum=0;
//		System.out.println("------------------------------");
		for(int i=start_i;i<start_i+n;i++) {
			for(int j=start_j;j<start_j+n;j++) {
				sum+=paper[i][j];
//				System.out.print(paper[i][j]+" ");
			}
//			System.out.println();
		}
		if(sum==n*n) {
			bluepaper++;
		}
		else if(sum==0) {
			whitepaper++;
		}
		else {
			function(start_i, start_j, n/2);
			function(start_i, start_j+n/2, n/2);
			function(start_i+n/2, start_j, n/2);
			function(start_i+n/2, start_j+n/2, n/2);
		}
	}
}

이 문제는 색종이를 4부분으로 나눠서 관찰하는 것을 반복해서 살펴볼 것입니다.

색종이를 4개의 사분면으로 나누고 각 사분면에서 색종이가 모두 0으로 되어 있으면 하얀색 색종이로 판단, 모두 1로 되어있으면 파란색 색종이로 판단, 그렇지 않으면 그 사분면을 다시 4 개의 사분면으로 나눠서 살펴봅니다.

함수를 이용해 이를 반복해 재귀적으로 호출하고, 마지막에 나눈 사분면의 크기가 1일 때 색종이가 0이면 하얀색, 1이면 파란색으로 판단해 수를 카운트해줍니다.