1. Problem 📃

[ 색종이 만들기 ]

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

[ 문제 ]

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

2. Input ⌨️

[ 입력 ]

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

3. Output 🖨

[ 출력 ]

첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.

4. Example 📚

[ 입출력 예시 ]

5. Solution 🔑

NN의 칸을 가진 정사각형을 쪼개면서 모든 칸의 색을 같은 색을 가질 때 한 장으로 치고 그렇지 않다면 N/2 N/2를 하며 탐색, 그렇지 않다면 또 탐색해서 결국 한 칸씩 본인의 색을 가질 때까지 나누어 각 색상의 개수를 구하면 되는 문제이다.

1. 종이의 색상을 담아줄 전역 2차원 배열(paper)을 선언해주고 종이 색상에 대한 변수 흰색(white)와 파란색(blue)을 0으로 초기화 하여 전역 변수를 선언해준다.
2. 정사각형 한 변의 길이를 나타낼 변수(N)을 입력받고 그에 대해 2차원 배열 paper의 크기를 [N][N]으로 정의해준다.
   그 후, paper 안에 색상 정보를 담아준다.

[ 종이를 탐색하여 단색의 종이인지 판별하기 위한 Search 메서드 ]
1. 매개변수는 시작 행과 시작 열을 담아준다. 그리고 8칸짜리 정사각형이라면 8칸을 확인할 것이므로 사이즈도 매개변수에 넣어준다.
2. 해당 종이이의 제일 첫번 째로 시작하는 칸의 색상을 color라는 변수에 담아준다. 칸을 탐색하면서 color와 다른 색상이 나타난다면 이 종이는 하나의 색으로 이루어진 온전한 색종이라 볼 수 없다.
3. 행열을 탐색한다. 범위는 행 + 사이즈에 열 + 사이즈로 이중 포문을 돌려 확인한다. 이 때 처음에 지정한 색상과 다른 색상이 나온다면 이 색종이는 false값을 반환하도록 하였고 모든 면을 탐색해서 잘 끝났다면 true값을 리턴하도록 하였다.

[ 색의 개수를 구하거나 커팅해줄 Cutting 메서드 ]
1. Cutting 메서드 또한 Search와 마찬가지로 동일한 매개변수를 넣어준다.
2. 위에서 Search메서드는 true 또는 false 값을 리턴하도록 하였다. 반환 값을 이용하기 위해 if문에 Search메서드에 매개변수를 담아 함수를 호출해본다.
3. true값이 나왔다 == "종이를 탐색했을 때 모두 같은 색이 발견되었다." 그럼 해당 종이색의 개수를 올리고 그 종이는 return 시켜 더 이상 쪼개지도, 탐색하지도 않게한다.
4. false값이 나왔다 == "종이를 탐색했을 때 다른 색이 발견되었다." 그럼 해당 사이즈를 반으로 잘라 종이를 같은 크기로 자르면 4면이 나오므로 시작점과 끝점을 각각 표시해주어 함수들을 다시 호출하여준다.

3. 최종 white와 blue 값을 출력해준다.

6. Code 💻

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

public class Main {

	public static int paper[][];
	
	public static int white = 0;
	public static int blue = 0;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken());
		
		paper = new int[N][N];
		
		for(int i=0; i< N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<N; j++) {
				paper[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		Cutting(0, 0, N);
		
		System.out.println(white);
		System.out.println(blue);
	}
	
	public static boolean Search(int row, int col, int size) {

		int color = paper[row][col];
		
		for(int i=row; i<row+size; i++) {
			for(int j=col; j<col+size; j++) {
				if(paper[i][j] != color) {
					return false;
				}
			}
		}
		return true;
	}
    
	public static void Cutting(int row, int col, int size) {
		
		if(Search(row, col, size)) {
			if(paper[row][col] == 0 ) {
				white++;
			}
			else if(paper[row][col] == 1){
				blue++;
			}
			return;
		}
		else {
			int newSize = size/2;
			
			Cutting(row, col, newSize);
			Cutting(row + newSize, col, newSize);
			Cutting(row, col + newSize, newSize);
			Cutting(row + newSize, col + newSize, newSize);
		}

	}
	

}