[Java] 백준 2630번: 색종이 만들기

문제

일단 생각하기!

• 같은 구역에 하나의 색만 있다면 그 색의 count++을 하고, 다른 색이 있다면 다시 정사각형의 형태가 되도록 4등분을 한다. 이때 재귀를 이용한 분할 정복 사용!

풀이

package BJ;

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

/**
 * 
 * @author 김유나
 * 2023-08-17
 * 
 * [문제] 백준 2630번 색종이 자르기
 * [아이디어] 재귀를 이용한 분할 정복을 사용하여 같은 구역에 하나의 색만 있다면 그 색의 count를 세고, 다른 색이 있다면 다시 정사각형이 되도록 4등분을 한다.
 *
 * 메모리 : 16,924kb 실행 시간 : 196ms
 */
public class BJ_2630_색종이만들기_김유나 {
	static int arr[][];
	static int white = 0, blue = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		// 전체 종이의 한 변의 길이 : 2의 제곱수(2, 4, 8, 16...)
		int n = Integer.parseInt(br.readLine());
		arr = new int[n][n]; // 0 또는 1로 이루어진 정사각형 배열
		
		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());
			}
		}
		
		confetti(0, 0, n);
		System.out.println(white + "\n" + blue);
		
	}
	static void confetti(int x, int y, int size) {
		int sum = 0;
		
		for (int i = x; i < x + size; i++) {
			for (int j = y; j < y + size; j++) {
				sum += arr[i][j];
			}
		}
		
		// 모두 하얀색인 공간 : 기저조건 
		if (sum == 0) white++;
		
		// 모두 파란색인 공간 : 기저조건
		else if (sum == size * size) blue++;
		
		// 파란색 또는 하얀색이 아닌 경우 : 다시 4분할
		else {
			// size를 반으로 나눈다.
			int half = size / 2;
			confetti(x, y, half); // 왼쪽 위 정사각형 : 1
			confetti(x, y + half, half); // 오른쪽 위 정사각형 : 2
			confetti(x + half, y, half); // 왼쪽 아래 정사각형 : 3
			confetti(x + half, y + half, half); // 오른쪽 아래 정사각형 : 4
		}
		
		
	}
	
}