백준 2630번 : 색종이 만들기(Java)

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

2630번: 색종이 만들기

---

[풀이]

 

- 분할 정복 및 재귀 유형의 문제입니다.
- 문제의 풀이 과정은 다음 프로세스입니다.
  1. 해당 배열이 1 혹은 0으로만 채워져 있는지 확인합니다.
  2. 만약, 하나의 숫자로만 채워져 있을 경우에는 재귀를 그만하고 종료합니다.
  3. 만약, 하나의 숫자로만 채워져 있지 않을 경우에는 재귀를 반복합니다.
- 한 변의 길이는 2의 n제곱승입니다. 따라서, n을 2로 나누면서 재귀의 범위를 줄여 나갑니다.
- 재귀되어가는 배열의 좌표는 (0,0) 부터 시작하여 n/2을 더해가며 진행합니다.
- 재귀가 종료될 때 숫자가 0, 1을 구분하여 각 전역변수 값을 1 더한 후, 최종적으로는 이 변수들을 출력합니다.

 

---

[코드]

 

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

public class Main {
	static int whiteCount,blueCount;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		int[][] arr = new int[n][n];
		whiteCount = 0;
		blueCount = 0;
		
		for(int i = 0; i< n; i++){
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			for(int j = 0; j< n; j++){
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		solve(arr,0,0,n );
		System.out.println(whiteCount);
		System.out.println(blueCount);
	}
	public static void solve(int[][] arr, int x, int y, int n){
		if(check(arr,x,y,n)){
			if(arr[x][y] == 0){
				whiteCount += 1;
			}else if(arr[x][y] == 1){
				blueCount += 1;
			}
			return;
		}
		
		solve(arr,x,y,n/2);
		solve(arr,x,y + n / 2, n / 2);
		solve(arr,x + n / 2, y, n / 2);
		solve(arr, x + n / 2, y + n / 2, n / 2);
	
	}
	
	public static boolean check(int[][] arr, int x, int y, int n){
		int checkNumber = arr[x][y];
		
		for(int i = x; i< x + n  ; i++){
			for(int j = y; j < y + n ; j++){
				if(arr[i][j] != checkNumber){
					return false;
				}
			}
		}
		return true;
	}
}