[JAVA]백준 2630 색종이 만들기

JAVA로 풀이했습니다.
출처 : 백준 알고리즘 https://www.acmicpc.net

문제 개요

2630번 문제 👉 https://www.acmicpc.net/problem/2630
색종이를 나누어 만들 수 있는 색종이 수 구하기
난이도 👉 실버 3

풀이과정

접근 방식은 재귀를 사용했습니다. 설계방식은 색종이에 접근하는 함수, 주어진 색종이가 온전한 색깔을 가지고 있는지 확인하는 함수로 구성하였습니다.

나만의 방법

먼저 색종이에 접근하는 함수는 인자로 처음 시작위치(i,j)와 가로,세로가 얼만큼의 너비를 가지고 있는지(w,h)를 인자로 가지고 있습니다. 이 함수는 주어진 색종이가 온전한 색깔을 가지고 있는지 확인하고 온전한 색깔을 가지고 있다면 counting을 하고, 아닌경우 더 작은 색종이에 접근하도록 자기자신을 호출하는 구조로 되어있습니다.

check하는 함수는 2중 for문으로 전체를 탐색하여 첫 원소와 나머지 원소가 같은지 비교하여 중간에 하나라도 아닌것이 발견되면 false, 이외에는 true처리를 했습니다.

소스코드

public class baek_2630 {
	static int N, arr[][], white, blue;

	static void paper(int i, int j, int w, int h) {
		if (check(i, j, w, h)) {
			if (arr[i][j] == 1) {
				blue++;
			} else if (arr[i][j] == 0) {
				white++;
			}
		} else {
			paper(i, j, w / 2, h / 2);
			paper(i + w / 2, j, w / 2, h / 2);
			paper(i, j + h / 2, w / 2, h / 2);
			paper(i + w / 2, j + h / 2, w / 2, h / 2);
		}
	}

	static boolean check(int i, int j, int w, int h) {
		int temp = arr[i][j];
		for(int k=i;k<i+w;k++) {
			for(int f=j;f<j+h;f++) {
				if(arr[k][f]!=temp) {
					return false;
				}
			}
		}
		return true;
	}

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